Merge Intervals
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Merge all overlapping intervals and return the non-overlapping result.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What if the intervals were sorted by start? Which ones can overlap the current one?
- Hint 2Only the last block you built can overlap with the next interval.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A calendar of meetings scribbled in random order. First sort them by start time. Now walk through: if the next meeting starts before the current block ends, it is the same busy block, so just stretch the block's end if needed. If it starts after, close the current block and start a new one.
- The obvious way
Compare every pair repeatedly until nothing merges: O(n²) or worse.
- The key insight
Sort by start. Keep a result list. For each interval: if it starts after the last result interval ends, add it as a new block; otherwise the two overlap, so set the last block's end to the larger of the two ends.
- The algorithm
- Sort intervals by start.
- Put the first interval in the result.
- For each next one: if its start <= last end, extend the last end to max(last end, its end).
- Otherwise append it as a new block.
Watch it run
Example[[1,3],[8,10],[2,6],[15,18]] (sorted: [1,3] [2,6] [8,10] [15,18])
Sort by start. The first block is 1-3.
result: 1-3
Where people slip
- Use max for the end: a later interval can sit entirely inside the current block.
- [1,4] and [4,5] touch and merge: the check is start <= last end.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def merge(intervals):
intervals.sort(key=lambda interval: interval[0]) # by start time
merged = [intervals[0]]
for start, end in intervals[1:]:
last = merged[-1]
if start <= last[1]:
last[1] = max(last[1], end) # same busy block: stretch it
else:
merged.append([start, end]) # a new block
return mergedNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.