Activity Selection (N Meetings)

Sort by finish time, book whatever frees the room soonest

time O(n log n)space O(n)

Picking the earliest-starting or the shortest meeting both fail on real inputs; the choice that is provably optimal is the one that FINISHES first. Among everything still bookable it frees the room no later than any rival, so any meeting a different pick could still fit, this pick can fit too — never worse, sometimes better. Sort by end time once, keep the time the room next comes free, and book a meeting only when it starts strictly after that. A meeting starting at the exact instant the previous one ends counts as a clash here.

Details

Animated on: meetings = M1(1,2), M2(3,8), M3(0,6), M4(8,10), M5(5,7), M6(2,4), M7(9,11) — one room, one meeting at a time, and a meeting may only start strictly after the previous one has ended. How many meetings can be held?

Problem:Activity Selection (N Meetings)Medium

Sort by finish time, book whatever frees the room soonest

step 1 / 10

M1 1..2

[0]

M2 3..8

[1]

M3 0..6

[2]

M4 8..10

[3]

M5 5..7

[4]

M6 2..4

[5]

M7 9..11

[6]

7 meetings want the same room, given in arbitrary order: M1(1,2), M2(3,8), M3(0,6), M4(8,10), M5(5,7), M6(2,4), M7(9,11). Only one can run at a time and a meeting must start strictly after the previous one ends, so the goal is the LARGEST count that fit, not the longest total time.

Pseudocode

1FUNCTION maxMeetings(meetings)
2  meetings <- SORT_BY_END(meetings)
3  count <- 0
4  lastEnd <- -INFINITY
5  chosen <- EMPTY LIST
6  FOR i <- 0 TO LENGTH(meetings) - 1
7    IF meetings[i].start > lastEnd
8      count <- count + 1
9      lastEnd <- meetings[i].end
10      APPEND meetings[i].id TO chosen
11  RETURN count

← / → step · space play · Home restart

Every step in words

Show all 10 steps

7 meetings want the same room, given in arbitrary order: M1(1,2), M2(3,8), M3(0,6), M4(8,10), M5(5,7), M6(2,4), M7(9,11). Only one can run at a time and a meeting must start strictly after the previous one ends, so the goal is the LARGEST count that fit, not the longest total time.
Sorted by FINISH time: 2, 4, 6, 7, 8, 10, 11. Whatever is still bookable, the meeting that frees the room earliest leaves the most time behind it — every later meeting a different choice could fit, this one fits too. That is why one left-to-right pass is enough and nothing is ever un-booked.
M1 finishes soonest of all 7, and nothing is booked yet, so waiting could only waste room time — book it. The room is now free from 2 onward. count = 1.
M6 wants to start at 2, the exact instant the room frees up — the rule is strictly after, so a back-to-back handover is still a clash and M6 is dropped. count stays 1.
M3 runs 0..6, which overlaps the booking that holds the room until 2, so it is dropped — spanning 6 units is exactly why it lost the room to shorter, earlier-finishing meetings. count stays 1.
M5 starts at 5, after the room frees up at 2, so it fits with no clash — book it. The room is now free from 7 onward. count = 2.
M2 runs 3..8, which overlaps the booking that holds the room until 7, so it is dropped — spanning 5 units is exactly why it lost the room to shorter, earlier-finishing meetings. count stays 2.
M4 starts at 8, after the room frees up at 7, so it fits with no clash — book it. The room is now free from 10 onward. count = 3.
M7 runs 9..11, which overlaps the booking that holds the room until 10, so it is dropped. count stays 3.
Pass finished: 3 meetings fit — M1, M5, M4 in that order. Every meeting that was dropped overlapped one already booked, and each booking freed the room as early as any alternative could, so no arrangement beats 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Activity Selection (N Meetings) in the editor All Greedy problems Back to roadmap