HANDS-ON · 60 minutes
Merge, insert, and count overlaps with the sort-then-sweep pattern — grounded in schedule conflict detection from Brandon's orchestration framework.
In my Python orchestration framework, jobs can be scheduled with time windows — a job might claim a GPU from time 5 to time 20, another from time 15 to time 30. Before I can allocate resources, I need to know which windows overlap and whether I can consolidate them. That is a merge-intervals problem, and it appears in nearly identical form in every system that deals with time ranges: calendar blocking, network packet coalescing, log window analysis.
My first attempt at the overlap check got the boundary conditions wrong — do [1,3] and [3,5] overlap? I assumed they didn't. The spec said they did. That kind of silent assumption is what makes interval problems feel slippery until the mental model locks in.
Interval problems feel intimidating until you internalize one insight: once you sort by start time, a single left-to-right pass resolves most of them. Imagine a sweep line moving left to right across a timeline — at each step, you either extend the current interval because the new one overlaps, or you seal the current interval and start a fresh one.
Sort by start time. Walk the list. If the current interval starts at or before the end of the last result interval, extend; otherwise, append a new interval.
Two edge cases to get right before you code: (1) Boundary conditions — do [1,3] and [3,5] overlap? It depends on whether the problem counts shared endpoints. Read the spec carefully; don't assume. (2) Python's sort — intervals.sort() on (start, end) pairs already sorts by start first, then end. You rarely need a custom key function.
gantt
title Interval Sweep — Before and After Merge
dateFormat X
axisFormat %s
section Input
[1,3] : 1, 3
[2,6] : 2, 6
[8,10] : 8, 10
section Merged
[1,6] : 1, 6
[8,10] : 8, 10Given a sorted, non-overlapping list, insert one new interval and re-merge. Three phases: copy all intervals that end before the new one starts, merge all intervals that overlap the new one, copy the rest.
When this bites: the boundary conditions for phases 1 and 2 are asymmetric. Phase 1 ends when intervals[i][1] < new[0] (strict less-than — the existing interval ends before the new one starts). Phase 2 merges when intervals[i][0] <= new[1] (less-than-or-equal — the existing interval starts at or before the new one ends). Swapping strict and non-strict here silently produces wrong output on inputs where endpoints touch.
A different question: given N meeting intervals, what is the minimum number of conference rooms required so every meeting runs simultaneously? This does not reduce to merge — merging answers "how many contiguous blocks?" not "how many rooms are running at peak?"
The heap approach: sort by start time. Use a min-heap of end times (one entry per room currently in use). For each meeting, if its start time is after the earliest end (heap top), the earliest-finishing room is free — reuse it. Otherwise, open a new room.
Analogy — the airport gate problem: each meeting is a flight using a gate. If a flight departs (ends) before a new flight arrives (starts), the gate is free. The min-heap tracks the earliest departure — the first gate that might be free. If no gate is free, open a new one. The maximum number of gates in use at any moment is the answer.
An alternative that avoids the heap: separate the start and end times into two sorted arrays, then walk them with two pointers. Increment rooms when a meeting starts before the next one ends; decrement when a meeting ends. The peak is the answer. Both approaches are O(N log N) — the heap approach generalizes more naturally to variants like "K tasks per resource."
Close the code and answer from memory:
new?[1,5] and [5,10] — do they overlap? It depends on what?Reflective prompt: My job scheduler computes windows where resources are claimed. When a new job arrives mid-stream, should I use merge-intervals or insert-interval — and why does the distinction matter? Think about what pre-conditions each algorithm requires (sorted? non-overlapping?) and what happens if those conditions are not met.
Application-level questions on interval merging, insertion, and resource counting
1. You have intervals [[3,5],[1,4],[6,9]]. After sorting by start time and running one merge pass, what do you get?
Correct Answer: A
After sorting: [[1,4],[3,5],[6,9]]. First merge: [1,4] starts the result. [3,5] — 3 <= 4, so extend to [1,5]. [6,9] — 6 > 5, so append. Result: [[1,5],[6,9]].
2. The problem says intervals [1,3] and [3,5] 'overlap if they share any point, including endpoints.' Which condition correctly detects overlap?
Correct Answer: B
If endpoints count as overlap, [1,3] and [3,5] overlap because 3 == 3. The merge condition must use <= : if current_start <= last_end, they overlap and you extend. Using strict < would miss this case.
3. You have sorted non-overlapping intervals [[1,3],[6,9]] and insert new interval [2,5]. What is the result?
Correct Answer: A
[1,3] and [2,5] overlap (2 <= 3), so merge to [1,5]. [6,9] does not overlap with [1,5], so append. Result: [[1,5],[6,9]].
4. To find the minimum number of conference rooms needed for intervals [[0,30],[5,10],[15,20]], which approach is most direct?
Correct Answer: B
Sort by start, then maintain a min-heap of end times. For each meeting, if it starts after the earliest end (heap top), reuse that room (pop and push new end). Otherwise open a new room (push). Peak heap size is the answer. Merging intervals answers a different question.
5. To find the minimum number of intervals to remove so the rest are non-overlapping, you should sort by:
Correct Answer: B
Sorting by earliest end time is the greedy key for maximizing the number of non-overlapping intervals (keeping the most = removing the fewest). An interval ending earlier leaves more room for the next one — the same exchange argument as interval scheduling.
6. Inserting a new interval into a sorted non-overlapping list of N intervals has what time complexity?
Correct Answer: B
Even though you can binary-search for the insertion position in O(log N), you may need to merge multiple overlapping intervals and shift the remaining elements. The overall pass is O(N). Resorting is O(N log N) but unnecessary — the list stays sorted after a single linear merge pass.
Problem: Given an array of intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you must remove so that the rest are non-overlapping.
Hint 1: Minimum removals = total intervals minus maximum non-overlapping intervals you can keep. Focus on maximizing the number you keep.
Hint 2: Sort by end time. Greedily keep each interval whose start is at or after the last kept interval's end. Count what you keep; subtract from total.