Interactive Lab · DSA & Algorithms

Sort once, sweep once, merge intervals and count meeting rooms in a single pass

A calendar full of meetings. Question 1: merge every overlapping block into one busy stretch. Question 2: how many meeting rooms do you need so nobody is double-booked? Comparing every pair is O(n²). The trick for both is the same two moves: sort by start time, then sweep a line from left to right, carrying just one small piece of state. For merging that's the “currently open block”; for rooms it's a counter that goes +1 at every start, −1 at every end. Its highest point is the answer. Drag the bars and watch both.

▶ Setup, the intervals

intervals 6

edit

Times run 0 → 20. Type pairs like 1-3, 2-6, 8-10, or drag a bar on the timeline below: grab the middle to move it, an end to stretch it.

▶ The playground, sort by start, then sweep left to right

step 0 / 0

🧭 Where this fits

Sort-then-sweep is how real calendars and schedulers think: Google Calendar's “busy” blocks are merged intervals, a conference-room booker is the rooms counter, and the same sweep finds peak concurrent users, max simultaneous DB connections, or how many servers a batch of jobs needs. In placement rounds it's Merge Intervals, Insert Interval, Meeting Rooms I/II, Non-overlapping Intervals and Minimum Arrows to Burst Balloons: one family, one move. The production version of the room count uses a min-heap of end times; the event sweep you're watching gives the same number.

The code that's actually running, sort, then one pass

🔮 Predict, then test

Load the ↺ classic example and switch to meeting rooms. Predict: what's the minimum number of rooms, and at what time does the counter peak? Then try this: two meetings 1-3 and 3-5. Merge mode glues them into 1-5 (they touch, so the busy stretch is unbroken), but meeting-rooms mode needs only one room, because the first meeting ends at 3 and the room is free for the next one. That's why the sweep processes an end before a start at the same timestamp. Change that tie-break and the answer goes up by one.

The takeaway

Your new mental model of interval problems

Sort first, and most of the problem disappears. Once intervals are ordered by start, an interval can only overlap the block you're currently building, never one you closed earlier. That turns O(n²) pair checks into one O(n) pass after an O(n log n) sort.
Merging carries one block. If the next start is ≤ the open block's end, extend the end with max(end, e) (a short interval inside a long one must not shrink it). Otherwise close the block and open a new one.
Rooms = peak overlap. Split every meeting into a +1 start event and a −1 end event, sort them, and run a counter. The maximum the counter ever reaches is exactly the number of rooms you need, and you can't do with fewer, since at that moment that many meetings are live at once.
Tie-breaks are the bug interviewers look for. Touching intervals: merge (closed) vs reuse a room (half-open). Decide which your problem means, then make the sort order say it.
Same sweep, more questions: the counter's peak is the max concurrency, the gaps between merged blocks are the free slots, and the room assignment (lowest free room first) is a valid schedule.

← Sliding Window Placement prep →Try: Binary Heap