Interval Patterns · Data Structures & Algorithms

Sort order is the whole game in interval problems. Get the key right and a greedy one-liner falls out; get it wrong and the same problem turns unsolvable. Non-overlapping Intervals is the tell. It asks for the minimum removals, which is the maximum set of non-overlapping intervals asked from the other side, and that greedy selection wants sort by end time, never start. Once you can hear which sort a problem is begging for, the algorithm mostly writes itself.

Problem 1: Non-Overlapping Intervals

Problem: Find the minimum number of intervals to remove to make the rest non-overlapping.

Example: [[1,2],[2,3],[3,4],[1,3]] -> Remove 1 ([1,3] overlaps with others)

Flip the question around. Removing the fewest intervals is the same as keeping the MAXIMUM number of non-overlapping ones, so removals = total - max_kept. Now you have a selection problem, which is much friendlier than a removal problem.

Why Sort by End Time?

You want each pick to leave the most room for the next one, and the interval that ends earliest leaves the most room. That's the entire justification for the sort key.

Consider: [[1,10], [2,3], [3,5]]
 
If we pick [1,10] first (ends late):
  - Can't pick [2,3] (overlaps)
  - Can't pick [3,5] (overlaps)
  - Total: 1 interval
 
If we pick [2,3] first (ends early):
  - Skip [1,10] (would overlap)
  - Pick [3,5] (doesn't overlap)
  - Total: 2 intervals
 
Greedy: always pick the interval that ends earliest!

Sort-by-End Greedy: Visual Walkthrough

Run the greedy selection on [[1,2],[2,3],[3,4],[1,3]]. Once it's sorted by end time, the decision is obvious at every step.

Input: Unsorted Intervals

Four intervals in random order. We need to find the minimum removals to eliminate all overlaps.

[1,2]

[2,3]

[3,4]

[1,3]

Unsorted -- can't do greedy yet

python

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])   # Sort by END time -- the key!
    removals = 0
    prev_end = float('-inf')

Sorted by end time, the greedy logic collapses to one question per interval: does this one start at or after where the last kept interval ended? If it does, no overlap, keep it and move the "last end" marker forward. If it doesn't, it collides with something you've already committed to, so this is the one that goes.

You might wonder why you always drop the current interval and never the one already kept. Because the kept interval ends earlier, so it leaves at least as much room for everything downstream. Trading it for a later-ending interval can only cost you future picks, never gain them, and that swap-can't-help argument is the whole proof that the greedy choice is optimal.

python

    for start, end in intervals:
        if start >= prev_end:            # No overlap -- keep it
            prev_end = end
        else:
            removals += 1               # Overlap -- remove it
    return removals

This is the Activity Selection problem from algorithms class. Greedy works because ending early maximizes future options. Sort by START for merging, sort by END for selection.

Problem 2: Remove Covered Intervals

Problem: Interval [a,b] is covered by [c,d] if c <= a and b <= d. Return the count of intervals that are NOT covered by any other.

Example: [[1,4],[3,6],[2,8]] -> 2 ([1,4] is covered by [2,8]? No. [3,6] is covered by [2,8]? Yes.)

The Sort Trick

The key is start ascending, with one twist: when two starts tie, break by end DESCENDING. That puts the longer interval first, already in hand to swallow the shorter ones sharing its start. Miss the tie-break and a covered interval sneaks through as if it were distinct.

[[1,4], [1,2], [3,6]]  ->  Sort by (start, -end)
[[1,4], [1,2], [3,6]]
 
Process [1,4]: prev_end = 4, count = 1
Process [1,2]: end=2 <= 4, COVERED, skip
Process [3,6]: end=6 > 4, NOT covered, count = 2, prev_end = 6
 
Answer: 2 remaining

python

def remove_covered_intervals(intervals):
    # Sort by start ASC, then end DESC
    intervals.sort(key=lambda x: (x[0], -x[1]))
    count = 0
    prev_end = 0
    for start, end in intervals:
        if end > prev_end:
            # Not covered - count it
            count += 1
            prev_end = end
        # If end <= prev_end, it's covered by a previous interval
    return count

Problem 3: Minimum Arrows (Burst Balloons)

Problem: Balloons have horizontal intervals. An arrow at x bursts all balloons containing x. Find minimum arrows to burst all balloons.

Example: [[10,16],[2,8],[1,6],[7,12]] -> 2 arrows

Read past the balloons and this is non-overlapping selection again. One arrow at the right x bursts every balloon that overlaps at that point, so "how many arrows?" is just "how many clumps of overlapping intervals?" asked in a different voice.

Same machine, then. Sort by end time and keep the current arrow as long as the next balloon still overlaps it. The moment a balloon starts past the arrow, that arrow can't reach it and you fire a fresh one. The only detail worth remembering is where you fire: at the end of the group's first balloon, the rightmost spot that still hits it, which gives you the best odds on whatever comes next.

python

def find_min_arrow_shots(points):
    if not points:
        return 0
    points.sort(key=lambda x: x[1])       # Sort by end time
    arrows = 1
    arrow_pos = points[0][1]              # Shoot at end of first balloon

The loop walks the balloons in end-time order and checks one thing: does this balloon start past the current arrow? If it does, the arrow misses, so bump the count and reposition the arrow at this balloon's end. Every balloon that starts at or before the arrow is already skewered, and you do nothing.

The forward pass works for the same reason the removal problem did. Ending each arrow as late as it can still land keeps every local choice optimal, and end-time sorting is what guarantees you never regret one. It's the exact same invariant from Non-overlapping Intervals, only the payoff is one fewer arrow instead of one fewer removal.

python

    for start, end in points[1:]:
        if start > arrow_pos:             # New group -- need another arrow
            arrows += 1
            arrow_pos = end
    return arrows

The pattern is identical to non-overlapping intervals. Sort by end, greedily shoot at the end of each group.

Problem 4: Sweep Line (Maximum Overlap)

Problem: Find the maximum number of overlapping intervals at any point.

Example: [[1,3],[2,4],[3,5]] -> At time 3, all three overlap. Answer: 3

The Sweep Line Idea

Sweep line throws out the whole idea of an interval as one object. Chop each one into two events instead: a "+1" at its start when another interval switches on, and a "-1" at its end when one switches off. Order every event by time and walk them once, carrying a running count of how many intervals are live at this instant.

The highest that count ever reaches is your answer. At any event, the count is exactly how many intervals contain that coordinate, so its peak is the maximum overlap anywhere on the line. What you've really done is trade a 2D question, comparing every pair of intervals, for a 1D scan: O(n log n) to sort the events, O(n) to sweep them.

Sweep Line: Visual Walkthrough

Run the sweep line on [[1,3],[2,4],[3,5]]. Decomposing intervals into events turns a messy overlap problem into a simple running counter.

Input: Three overlapping intervals

[1,3], [2,4], [3,5]. How many overlap at the busiest moment?

[1,3]

[2,4]

[3,5]

Need to find maximum concurrency

python

def max_overlap(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))    # Interval begins -- one more active
        events.append((end, -1))     # Interval ends -- one fewer active
    events.sort()                    # Process events in time order
    max_count = current = 0
    for time, delta in events:
        current += delta             # Update running count
        max_count = max(max_count, current)  # Track the peak
    return max_count

Turning intervals into events answers "how many are active right now?" with nothing more than a running count.

Tie-breaking matters. When a start and end event share a coordinate, does the ending interval still count as active? If you want it to (inclusive boundaries), sort ends after starts at that coordinate: (time, -1) before (time, +1) won't work, because you need starts first. The default tuple sort handles this: (3, -1) comes before (3, 1), so ends are processed first. If you want starts first (inclusive), use (time, 1) vs (time, -1) and reverse the sort.

Problem 5: Employee Free Time

Problem: Given schedules for multiple employees, find the common free time (gaps where NO ONE is working).

Forget which employee owns which block. Pour every work interval onto one shared timeline and the problem shrinks. If A works 9 to 12 and B works 11 to 14, their combined coverage is a solid 9 to 14 with no seam in the middle. Free time is only where that coverage has a hole, so what you want is the gaps in everyone's merged schedule.

Three moves. Flatten every interval into one list and drop the employee labels, merge the overlaps to get the combined busy blocks, then read off the spaces between consecutive merged blocks. Those spaces are the windows when nobody is on the clock. That flatten-merge-gaps pipeline is worth memorizing; it answers any "uncovered region across many sources" question.

python

def employee_free_time(schedule):
    all_intervals = []
    for employee in schedule:
        all_intervals.extend(employee)   # Flatten all schedules
    all_intervals.sort()                 # Sort by start time
    merged = [all_intervals[0]]          # Seed with first interval
    for interval in all_intervals[1:]:
        if interval[0] <= merged[-1][1]: # Overlapping -- extend
            merged[-1][1] = max(merged[-1][1], interval[1])
        else:
            merged.append(interval)      # Gap -- new interval

Merging leaves a clean list of non-overlapping blocks covering every moment someone is working. The free time lives in the cracks between them, from where one block ends to where the next begins. Each crack is a stretch when nobody has a commitment.

Pulling those cracks out is one linear pass over consecutive blocks. Given [1,5], [8,12], [15,20], the free windows are [5,8] and [12,15]: end of the previous block to start of the next, every time.

python

    free_time = []
    for i in range(1, len(merged)):
        gap = [merged[i-1][1], merged[i][0]]  # End of prev to start of next
        free_time.append(gap)
    return free_time

Flatten, merge, read the gaps. Reach for that sequence whenever a problem hides its answer in the space between many overlapping schedules.

Pattern Recognition

"Remove minimum to make non-overlapping"

Sort by END, greedy select

Equivalent to max non-overlapping selection

"Remove covered intervals"

Sort by start, then -end

Longer intervals first to cover shorter ones

"Minimum arrows/groups"

Sort by END, count groups

Same as non-overlapping: one per group

"Maximum overlap at any point"

Sweep line (+1/-1 events)

Convert to events, track running count

"Find gaps/free time"

Merge all, return gaps

Gaps between merged intervals

Practice

Apply the greedy approach: keep the interval that ends earliest to maximize room for future intervals.

Try it yourself

Non-Overlapping Intervals

Given an array of intervals, return the minimum number of intervals you need to remove to make the rest non-overlapping.

Examples

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Remove [1,3]

Input: intervals = [[1,2],[1,2],[1,2]]

Output: 2

Remove two of the three

Non-Overlapping Intervals

Click "Run" to execute your code

Test Cases

Input: [[1,2],[2,3],[3,4],[1,3]]Expected: 1

Input: [[1,2],[1,2],[1,2]]Expected: 2

Input: [[1,2],[2,3]]Expected: 0

Solution

def solution(nums, target):

left, right = 0, len(nums) - 1

while left <= right:

mid = left + (right - left) // 2

if nums[mid] == target:

return mid

elif nums[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

# Time: O(log n) | Space: O(1)

View Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

Beyond Basic Merging

Pick the sort key and the greedy usually appears on its own. Go by END when you're selecting the most non-overlapping intervals, by START (with a -end tie-break) when you're testing coverage. When the question is about overlap counts rather than the intervals themselves, stop sorting intervals and sweep events instead.

Key Takeaways

Sort by END for max non-overlapping selection
Sort by (start, -end) for covered interval problems
Sweep line: +1 at start, -1 at end, track max
Free time = gaps after merging all intervals

Next: Intervals Mastery

Problem 1: Non-Overlapping Intervals

Why Sort by End Time?

Sort-by-End Greedy: Visual Walkthrough

Problem 2: Remove Covered Intervals

The Sort Trick

Problem 3: Minimum Arrows (Burst Balloons)

Problem 4: Sweep Line (Maximum Overlap)

The Sweep Line Idea

Sweep Line: Visual Walkthrough

Problem 5: Employee Free Time

Pattern Recognition

Practice

Non-Overlapping Intervals

Solution

View Solution

Want More Practice?

Beyond Basic Merging

Key Takeaways