​

Interval Problems

​

Key Technique: Sort First

​

Core Patterns

​

1. Merge Intervals

def merge(intervals):
    intervals.sort()
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

​

2. Insert Interval

​

3. Interval Intersection

​

4. Meeting Rooms (Overlap Check)

• Can attend all? — sort by start, check for any overlap
• Min rooms needed? — use a min-heap or sweep line on start/end events

​

5. Sweep Line

events = []
for start, end in intervals:
    events.append((start, 1))   # interval starts
    events.append((end, -1))    # interval ends
events.sort()

​

Complexity

​

Classic Problems

• Merge Intervals
• Insert Interval
• Non-overlapping Intervals (min removals)
• Meeting Rooms I & II
• Minimum Number of Arrows to Burst Balloons
• Interval List Intersections
• Employee Free Time
• My Calendar I, II, III

​

When to Use

• Problems involving time ranges, schedules, or bookings
• Overlapping or conflicting range detection
• Resource allocation (rooms, CPUs, etc.)
• Any problem with [start, end] pair inputs