Greedy & Intervals

Intervals

Sort intervals and sweep to merge, insert, or count overlaps.

Medium, about 75 minutes to practise.

1Understand

The idea

Sort intervals by start (or by end, when choosing how many to keep), then sweep from left to right. Two neighbours overlap when the next one starts before the current one ends, so merging, inserting and counting overlaps become a single pass. For "how many at once", sort the start and end events separately.

Intuition

Sort intervals by start (or by end when selecting how many to keep), then sweep left to right. Two neighbours overlap when the next starts before the current ends, merging, inserting and conflict counts become one pass.

For "how many overlap at once". Treat starts and ends as separate events, sort them, and sweep a counter. Sorting by end is the classic activity-selection greedy.

Draw the intervals on a line; the sweep is just reading that picture left to right.

What you will be able to do

  • Define overlap precisely (touching?)
  • Use a heap or sweep line for concurrent counts

When to use it

  • Merge overlapping ranges
  • Meeting rooms
  • Minimum removals to avoid overlap

2See it

Walkthrough

Merge overlapping intervals

[[1,3],[2,6],[8,10]], sort, then extend or append.

1 / 6

i
1-3
2-6
8-10
012

Sort by start. merged starts empty.

intervals.sort()

Live template

Line 1 active

1intervals.sort()
2merged = []
3for s, e in intervals:
4 if merged and s <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], e)
5 else: merged.append([s, e])

Complexity: time O(n log n), space O(n)

O(n log n) from sorting, then O(n). Pairwise checks are O(n²). Sweep-line event sorting is the right tool when the question is occupancy over time, not just merge.

Read the walkthrough as text

Merge intervals. [[1,3],[2,6],[8,10],[15,18]].

  1. Sort by start (already sorted).
  2. Seed result with [1,3]. Next [2,6] overlaps (2 ≤ 3) → extend end to 6.
  3. [8,10] does not overlap → append. Same for [15,18].
  4. Result [[1,6],[8,10],[15,18]].

Meeting-rooms II: sort start and end arrays; increment on start, decrement on end, track peak count.

3Recognise it

Kinds of problems (10)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Merge intervals

    Example. Merge all overlapping intervals.

    How. Sort by start; extend last end if overlap else append new interval.

  • Insert an interval

    Example. Insert new interval into sorted non-overlapping list.

    How. One pass: append before, merge middle overlaps, append rest.

  • Non-overlapping intervals (min removals)

    Example. Fewest intervals to remove so none overlap.

    How. Sort by end; keep interval if start ≥ last end (activity selection).

  • Meeting rooms (max concurrency)

    Example. Maximum simultaneous meetings.

    How. Sort starts and ends; sweep with two pointers counting active.

  • Interval intersections of two lists

    Example. All overlaps between two interval lists.

    How. Two pointers: advance list with earlier end; record max(starts) to min(ends).

  • Sweep line over start and end events

    Example. Count online users or overlap depth.

    How. Events +1 at start, −1 at end; sort and prefix max.

  • Answer queries with the smallest covering interval

    Example. Shortest interval containing at least k listed points.

    How. Sort by start; slide end while coverage count ≥ k.

  • Sort by start, then by end descending (covered intervals)

    Example. Count covered intervals, parent contains child.

    How. Sort start asc, end desc; stack or sweep to drop dominated intervals.

  • Keep disjoint intervals in a sorted structure

    Example. My Calendar I/II, insert if no triple overlap.

    How. Sorted list or tree map of intervals; binary search neighbours for overlap.

  • Skyline (sweep line with a heap)

    Example. Building skyline silhouette.

    How. Sort events; heap of active heights; on end remove lazy or multiset height.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Touching intervals

    Why it happens. [1,2] and [2,3] overlap or not depending on who you ask.

    How it fails. Merge treats touching as overlap but removal counts as overlap, inconsistent answer.

    Fix. Read statement: merge often uses s <= last_end; non-overlap may require s > last_end.

  • End not maximised

    Why it happens. Overwrite merged end with new interval’s end looks like “latest finish”.

    How it fails. Merge [1,5] with [2,3] → [1,3] shrinks cover, should be [1,5].

    Fix. On overlap: merged[-1][1] = max(merged[-1][1], e).

  • Not sorted first

    Why it happens. One pass scanning in input order feels like a sweep.

    How it fails. Later interval [0,1] after [3,4] never merges with earlier middle overlap.

    Fix. Sort by start (or end per problem) before linear scan.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons