Intervals

Medium

Time: O(n log n) for sortingSpace: O(n)

0/7

problems solved

Introduction to Interval Problems

Interval problems involve ranges defined by a start and end point. The key insight is that sorting transforms chaos into order.

Common interval problem types:

•Merge overlapping intervals - Combine intervals that share common time
•Meeting rooms - Count concurrent events or check for conflicts
•Non-overlapping selection - Select maximum intervals without overlap
•Interval intersection - Find common time between interval lists

The first decision in any interval problem: What should I sort by?

Goal	Sort By	Why
Merge overlapping	Start time	Process left-to-right, extend when overlapping
Max non-overlapping	End time	Greedy: earliest ending leaves most room
Meeting rooms	Start AND End (sweep line)	Track concurrent meetings

Merge Overlapping Intervals

The classic merge intervals pattern: combine all overlapping intervals into one.

The Algorithm:

•Sort by start time
•Initialize result with first interval
•For each interval: if it overlaps with last result, merge them; otherwise add new interval

Overlap condition: curr.start <= prev.end

Why <= not <? Because [1,2] and [2,3] are considered overlapping (they share point 2).

Input: [[1,3], [2,6], [8,10], [15,18]]

Sorted: [[1,3], [2,6], [8,10], [15,18]] (already sorted)

Step 1: result = [[1,3]]

Step 2: [2,6] overlaps with [1,3] (2 <= 3) → merge to [1,6]

result = [[1,6]]

Step 3: [8,10] doesn't overlap (8 > 6) → add

result = [[1,6], [8,10]]

Step 4: [15,18] doesn't overlap (15 > 10) → add

result = [[1,6], [8,10], [15,18]]

Code

Java

▶ Interactive Merge Intervals

Merge Intervals

Sort by start time, then merge overlapping intervals

Speed:

Input Intervals (on timeline):

Merged Result:

Merged intervals will appear here

Input Count

Result Count

0/0

Processed

Click Play to merge overlapping intervals

Key Insight: Sort by start time, then check if curr.start <= prev.end. If overlap, merge by extending end to max(prev.end, curr.end).

Insert Interval

Given a sorted list of non-overlapping intervals, insert a new interval and merge if necessary.

Three phases:

•Add all intervals that end before new interval starts
•Merge all intervals that overlap with new interval
•Add all remaining intervals

Intervals: [[1,2], [3,5], [6,7], [8,10], [12,16]]

New: [4,8]

Phase 1: [1,2] ends before [4,8] starts → add [1,2]

Phase 2: [3,5] overlaps → merge to [3,8]

[6,7] overlaps → merge to [3,8]

[8,10] overlaps → merge to [3,10]

Phase 3: [12,16] starts after merged ends → add [12,16]

Result: [[1,2], [3,10], [12,16]]

Code

Java

Meeting Rooms: Line Sweep

Meeting Rooms I: Can a person attend all meetings? (Check for any overlap)

Meeting Rooms II: Minimum rooms needed? (Find max concurrent meetings)

The elegant solution uses Line Sweep: treat each start as +1 room, each end as -1 room.

Meetings: [[0,30], [5,10], [15,20]]

Events: (0, +1), (5, +1), (10, -1), (15, +1), (20, -1), (30, -1)

Sorted: (0, +1), (5, +1), (10, -1), (15, +1), (20, -1), (30, -1)

Time 0: rooms = 1 (meeting 1 starts)

Time 5: rooms = 2 (meeting 2 starts) ← MAX!

Time 10: rooms = 1 (meeting 2 ends)

Time 15: rooms = 2 (meeting 3 starts) ← MAX!

Time 20: rooms = 1 (meeting 3 ends)

Time 30: rooms = 0 (meeting 1 ends)

Answer: 2 rooms needed

Tie-breaking: When start and end have same time, process end first (-1 before +1). A meeting ending at time T frees the room for a meeting starting at time T.

Code

Java

▶ Interactive Meeting Rooms

Meeting Rooms II

Line Sweep: Count concurrent meetings with +1/-1 events

Speed:

Meetings:

Events (sorted by time):

Events will be created...

Current Active Rooms

Max Rooms Needed

Meetings

Events

0/0

Processed

Click Play to find minimum meeting rooms

Key Insight: Treat each start as +1, each end as -1. Sort events by time (ends before starts at same time). Sweep through and track max concurrent meetings.

Non-overlapping Selection (Greedy)

Select the maximum number of non-overlapping intervals. This is the classic activity selection / scheduling problem.

Key insight: Sort by END time, greedily pick earliest-ending intervals.

Why end time? An interval that ends early leaves more room for future intervals.

Intervals: [[1,4], [2,3], [3,5], [4,6]]

Sorted by end: [[2,3], [1,4], [3,5], [4,6]]

Pick [2,3] → prevEnd = 3

[1,4] starts at 1 < 3 → overlaps, skip

[3,5] starts at 3 >= 3 → pick! prevEnd = 5

[4,6] starts at 4 < 5 → overlaps, skip

Max non-overlapping: 2 intervals ([2,3] and [3,5])

Related problem: Minimum intervals to remove = Total - Max non-overlapping

Code

Java

Interval List Intersection

Given two lists of sorted, non-overlapping intervals, find all intersections.

Two-pointer approach:

•Compute intersection: [max(start1, start2), min(end1, end2)]
•If valid intersection (start <= end), add to result
•Advance the pointer with smaller end time

A: [[0,2], [5,10], [13,23], [24,25]]

B: [[1,5], [8,12], [15,24], [25,26]]

i=0, j=0: A[0]=[0,2], B[0]=[1,5]

intersection = [max(0,1), min(2,5)] = [1,2] ✓

A ends first (2 < 5), i++

i=1, j=0: A[1]=[5,10], B[0]=[1,5]

intersection = [max(5,1), min(10,5)] = [5,5] ✓

B ends first (5 < 10), j++

i=1, j=1: A[1]=[5,10], B[1]=[8,12]

intersection = [max(5,8), min(10,12)] = [8,10] ✓

A ends first (10 < 12), i++

... and so on

Result: [[1,2], [5,5], [8,10], [15,23], [24,24], [25,25]]

Code

Java

▶ Interactive Interval Intersection

Interval List Intersection

Two pointers: advance the interval that ends first

Speed:

AList A (sorted, non-overlapping)

[0,2]

[5,10]

[13,23]

BList B (sorted, non-overlapping)

[1,5]

[8,12]

[15,24]

Intersections found:

Intersections will appear here...

Pointer A

Pointer B

Intersections

Click Play to find interval intersections

Key Insight: Intersection = [max(a.start, b.start), min(a.end, b.end)]. Valid if start <= end. Advance the pointer with smaller end time.

Minimum Arrows to Burst Balloons

Each balloon is an interval on x-axis. An arrow shot at x bursts all balloons where start <= x <= end. Find minimum arrows to burst all balloons.

This is maximum non-overlapping in disguise! Each arrow can burst all overlapping balloons.

Minimum arrows = Number of non-overlapping groups

Key difference from standard non-overlap: Here, touching endpoints ARE overlapping (arrow at point 2 bursts both [1,2] and [2,3]).

Code

Java

Employee Free Time

Given multiple employees' working schedules, find all common free time intervals.

Approach: Merge all working intervals, then find gaps.

Steps:

•Flatten all schedules into one list
•Sort by start time
•Merge overlapping work intervals
•The gaps between merged intervals are free time

Example:

Employee 1: [[1,2], [5,6]]

Employee 2: [[1,3]]

Employee 3: [[4,10]]

Flattened: [[1,2], [5,6], [1,3], [4,10]]

Sorted: [[1,2], [1,3], [4,10], [5,6]]

Merged: [[1,3], [4,10]]

Free time: [[3,4]] (gap between 3 and 4)

Code

Java

Common Edge Cases

Edge Cases to Handle:

1. Empty Input

if (intervals.length === 0) return [];

2. Single Interval

if (intervals.length === 1) return intervals;

3. All Intervals Overlap

[[1,10], [2,5], [3,7]] → [[1,10]]

4. No Intervals Overlap

[[1,2], [5,6], [8,9]] → [[1,2], [5,6], [8,9]]

5. Touching Intervals

Merge: [[1,2], [2,3]] → [[1,3]] (touching = overlapping)

Non-overlap: [[1,2], [2,3]] → NOT overlapping (depends on problem)

Common Mistakes:

Mistake	Consequence
Not sorting first	Wrong merge results
Using `<` vs `<=` wrong	Incorrect overlap detection
Forgetting `max()` for merge	Merged interval too short
Sorting by wrong key	Greedy selection fails
Integer overflow in Java	Use `Integer.compare()`

10.

Choosing the Right Approach

Quick reference for interval problems:

Problem Type	Sort By	Technique
Merge overlapping	Start	Extend end when overlapping
Insert interval	Already sorted	Three-phase merge
Meeting Rooms I	Start	Check adjacent overlap
Meeting Rooms II	Events	Line sweep (+1/-1)
Max non-overlapping	End	Greedy selection
Min intervals to remove	End	Total - Max non-overlapping
Interval intersection	Already sorted	Two pointers
Min arrows (balloons)	End	Count non-overlapping groups
Employee free time	Start	Merge all, find gaps

Decision Framework:

Need to combine intervals? → Merge (sort by start)

Need max non-overlapping? → Greedy (sort by end)

Need concurrent count? → Line sweep (+1/-1 events)

Two sorted lists? → Two pointers

Common Mistakes:

•Using < instead of <= for overlap (check problem definition)
•Forgetting to update merged interval's end with max()
•Sorting by wrong attribute (start vs end)
•Not handling empty input

11.

Template Summary

Merge Overlapping Template:

function merge(intervals):

sort intervals by start time

result = [first interval]

for each interval:

if overlaps with last result:

extend last result's end

else:

add as new interval

return result

Line Sweep Template:

function countConcurrent(intervals):

events = []

for [start, end] in intervals:

events.add((start, +1)) // start

events.add((end, -1)) // end

sort events by time (end before start if tied)

count = maxCount = 0

for (time, delta) in events:

count += delta

maxCount = max(maxCount, count)

return maxCount

Greedy Non-overlap Template:

function maxNonOverlap(intervals):

sort intervals by END time

count = 1

prevEnd = intervals[0].end

for i from 1 to n:

if intervals[i].start >= prevEnd:

count++

prevEnd = intervals[i].end

return count

Interval Intersection Template:

function intersect(A, B):

i = j = 0

result = []

while i < A.length and j < B.length:

start = max(A[i].start, B[j].start)

end = min(A[i].end, B[j].end)

if start <= end:

result.add([start, end])

// Advance pointer with smaller end

if A[i].end < B[j].end: i++

else: j++

return result

Interview Tips:

•Always clarify overlap definition (<= vs <)
•Draw timeline diagrams
•Consider edge cases: empty, single, all overlapping

Test Your Knowledge

Take a quick 15question quiz to test what you've learned.