top of page

Union of intervals vs. meeting rooms: two greedy patterns

Nov 3
2 min read

Interval problems show up constantly in coding interviews, and two of the most common ones look similar but ask different questions. Merging overlapping intervals asks what the union looks like. Meeting rooms asks how many things happen at once. Both yield to greedy thinking once you pick the right sort order.

Pattern one: union of intervals. Sort the intervals by start time. Keep a current interval, and for each next interval, if its start is at or before the current end, extend the end with the maximum of the two ends. Otherwise, push the current interval to the result and start a new one. The sort dominates the cost, so the total is O(n log n) time with O(n) output space. The key insight is that after sorting by start, only the last merged interval can overlap the next one.

Pattern two: meeting rooms. Here the question is how many intervals overlap at once. Sort starts and ends separately and sweep with two pointers, adding a room only when a start comes before the earliest end. A min-heap of end times gives the same answer and is easy to explain on a whiteboard. Both patterns cost O(n log n).

Choosing between them: if the prompt wants merged coverage or gaps, think union; if it wants a count or capacity, think meeting rooms. Two intervals overlap when the later start is less than the earlier end, and touching endpoints usually do not count.

Rehearse the explanation out loud as well as the code. A tool like an AI interview helper can simulate a live interview while you practice, so that the pattern recognition becomes automatic before the real call.

A good drill is to solve both problems back to back on the same input, then explain why the sort key differs. Union sorts by start because you merge left to right; meeting rooms tracks ends because rooms free up as time moves forward. Naming that difference clearly is what interviewers listen for.

Written by the AI Interview Copilot team.

 
 
 

Recent Posts

See All
Image Smoother (LeetCode 661): Clean Neighbor Loops

For each cell of a grayscale image, replace it with the floor of the average of itself and its up to eight neighbors. Idea Loop over the 3x3 block around each cell, skip coordinates outside the grid,

 
 
 

Comments


bottom of page