📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!
  • google app store apple app store
    • ✖

      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