Intervals

MediumArray~2 days

Moderate

progress0 / 7 solved

Sort by start, then sweep. Merge overlaps, detect conflicts, insert cleanly.

Prerequisites

← Heap / Priority Queue ← Greedy

Concept

Interval problems involve ranges [start, end]. The core operation is merging overlapping intervals. Sort by start time first — then sweeping left to right, you know that if the current interval's start ≤ previous interval's end, they overlap.

When to use this pattern

◆Merging overlapping meetings or ranges
◆Checking if someone is available at a time
◆Inserting a new interval into a sorted list
◆Minimum number of meeting rooms needed

Common patterns

Sort + merge

Sort by start. Extend current interval's end or push new interval.

Insert interval

Find insertion point; merge with overlapping neighbors.

Sweep line

Event-based: +1 on start, -1 on end. Scan for peak overlap.

Brute force → optimal thinking

Brute force

Compare every pair of intervals → O(n²).

Observation

After sorting by start, each interval can only overlap with the previously processed interval.

Optimization

Sort O(n log n), then single pass O(n): if intervals overlap, extend the end; otherwise push and move on.

Final complexity

O(n log n) dominated by sorting.

Quick Recall Check

What is the first step in most interval problems?

Two intervals [a,b] and [c,d] overlap when:

To find the minimum number of meeting rooms needed, which data structure helps?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

Can you merge intervals in one sorted pass?Do you know the difference between touching and overlapping intervals?Can you solve Meeting Rooms II with a min-heap?

Progress is saved on this device