Pattern visualizer
N Meetings in One Room
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. 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?.
Sort by finish time, book whatever frees the room soonest
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.
1FUNCTION maxMeetings(meetings)2 meetings <- SORT_BY_END(meetings)3 count <- 04 lastEnd <- -INFINITY5 chosen <- EMPTY LIST6 FOR i <- 0 TO LENGTH(meetings) - 17 IF meetings[i].start > lastEnd8 count <- count + 19 lastEnd <- meetings[i].end10 APPEND meetings[i].id TO chosen11 RETURN count
← / → step · space play · Home restart