📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    A company needs to schedule a maximum number of meetings

    in a single conference room. Each meeting `i` has a start time `s_i` and an finish time `f_i`. Once a meeting starts, it must run to completion.     Consider the following greedy strategy:     1.  Sort all meetings by their start times in ascending order.     2.  Select the first meeting.     3.  From the remaining meetings, select the next meeting that starts after the previously selected meeting finishes.     4.  Repeat until no more meetings can be selected.     Given the meetings: `(s, f)`   `M1: (1, 4)`     `M2: (3, 5)`     `M3: (0, 6)`     `M4: (5, 7)`     `M5: (8, 9)`     `M6: (5, 9)`     Which set of meetings will be selected by the described greedy strategy? 
    A `M1, M4, M5` Correct Answer Incorrect Answer
    B `M3, M5` Correct Answer Incorrect Answer
    C `M1, M2, M4` Correct Answer Incorrect Answer
    D `M1, M6` Correct Answer Incorrect Answer

    Solution

    Answer : B)`M3: (0, 6)`         `M1: (1, 4)`         `M2: (3, 5)`         `M4: (5, 7)`         `M6: (5, 9)`         `M5: (8, 9)`         1. Select `M3 (0, 6)`. Current end time = 6.         2. Iterate through remaining:            `M1 (1, 4)`: `1 < 6` (cannot select)            `M2 (3, 5)`: `3 < 6` (cannot select)            `M4 (5, 7)`: `5 < 6` (cannot select)            `M6 (5, 9)`: `5 < 6` (cannot select)            `M5 (8, 9)`: `8 >= 6` (can select). Select `M5`. Current end time = 9.         3. No more meetings.         Selected: `M3, M5`. 

    Practice Next
    More IT DBMS Questions
    ask-question