Most meetings in one room
Fit the greatest number of meetings into one room by always keeping the one that ends first. About 15 minutes.
Which meeting first?
One room, many requests. You want to host as many meetings as possible, and two meetings cannot overlap. A meeting that ends at 5 and one that starts at 5 do not clash.
Starting earliest does not work: one long meeting could block everything. Shortest first can fail too. The safe choice is the meeting that ends first, because it frees the room as early as possible.
Sort by end, then sweep
Sort all meetings by their end time. Walk through them, remembering when the last kept meeting ended.
If the next meeting starts at or after that moment, keep it and update the moment. Otherwise it clashes with a kept one, so skip it. Never go back and change a choice, since an earlier end can never be worse.
meetings.sort(key=lambda m: m[1])
last = -1
count = 0
for start, end in meetings:
if start >= last:
count += 1
last = end[1, 3] ends first, so keep it. The room is busy until 3.
Meetings [1, 4], [2, 3], [3, 5]. Sorted by end, what is the most you can hold?
- A2, the meetings [2, 3] and [3, 5]
- B1
- C3
Show the answer
2, the meetings [2, 3] and [3, 5]. [2, 3] ends first. [3, 5] starts at 3, so it fits. [1, 4] then clashes with both.
Most meetings
You are given a list of meetings, each as [start, end]. A room can hold one meeting at a time, and a meeting that starts exactly when another ends does not clash with it. Return the largest number of meetings you can hold.
meetings = [[1, 3], [2, 5], [4, 6], [6, 8], [5, 9]] → 3
0 ≤ meetings.length ≤ 100,000 · 0 ≤ start < end ≤ 1,000,000,000