Merging overlapping meetings, scheduling rooms, finding conflicts in timelines. Interval problems are everywhere in real software — calendars, resource allocation, even collision detection. Once you see the pattern, they're surprisingly formulaic.
IntermediateAn interval is a pair [start, end] representing a continuous range on a number line. Could be a meeting from 9:00 to 10:30, a block of reserved memory addresses, a segment on a chromosome, or a booking at a restaurant. The start and end might be integers, floats, timestamps — doesn't matter. The structure is always the same.
Interval problems ask you to do things with collections of these ranges: merge overlapping ones, find conflicts, insert new ones, count how many overlap at any point, or select the maximum number of non-overlapping intervals.
These problems are everywhere in production software. Google Calendar merges overlapping events. Operating systems manage memory as intervals. CDN cache invalidation involves overlapping time ranges. Video editors lay clips on a timeline. IP firewalls merge overlapping CIDR blocks. If you build software, you will encounter interval problems.
The good news: interval problems are extremely pattern-driven. Nearly every one starts the same way — sort by start time. Once sorted, overlapping intervals are adjacent, making them much easier to process in a single scan.
Input: [[1,3], [8,10], [2,6], [15,18]]. We want non-overlapping merged intervals.
That's it. Sort + single pass. After sorting by start, you only need to check if the current interval's start ≤ the last merged interval's end. If yes, merge (extend the end). If no, start a new group.
Edge case: What about [[1,4], [2,3]]? The second interval is entirely contained within the first. After sorting, [2,3]'s start (2) ≤ [1,4]'s end (4), so we merge. The end becomes max(4, 3) = 4. The result is [[1,4]]. Correct — the contained interval was absorbed.
The sweep line is a conceptual vertical line that sweeps from left to right across the number line. Instead of thinking about intervals as pairs, think of them as two events:
Procedure:
Example: meetings [[0,30], [5,10], [15,20]]. Events: (0,+1), (5,+1), (10,-1), (15,+1), (20,-1), (30,-1). Scanning: counter goes 1 → 2 → 1 → 2 → 1 → 0. Peak = 2. You need 2 rooms.
Given a sorted, non-overlapping list and a new interval to insert:
The overlap condition in phase 2: existing interval [a,b] overlaps with new interval [c,d] when a ≤ d and c ≤ b. Since the list is sorted, once you hit an interval that starts after the new interval ends, you're done with phase 2.
Problem: given n intervals, select the maximum number that don't overlap. This is the classic activity selection problem.
The greedy strategy: sort by end time (not start time!). Greedily pick the earliest-ending interval that doesn't conflict with the last picked one. Why end time? Because picking the interval that finishes earliest leaves the most room for future intervals.
Proof of optimality: suppose the greedy solution is suboptimal. The first difference between greedy and optimal must be a case where optimal picks a later-ending interval. But swapping to the earlier-ending one can only help (or not hurt) future selections. By induction, greedy matches or beats optimal at every step.
An alternative to sweep line for "minimum rooms needed": sort by start time and use a min-heap of end times. For each meeting:
The heap size at any point = number of rooms in use. The maximum heap size = answer. This approach is equivalent to sweep line but sometimes easier to implement for related queries (like "which room is each meeting in?").
merged[-1][1] = max(merged[-1][1], current_end), not merged[-1][1] = current_end. The current interval's end might be before the merged interval's end (containment case).
a.start <= b.end treats touching as overlapping. Use a.start < b.end if touching doesn't count.
| Operation | Time | Space | Notes |
|---|---|---|---|
| Merge Intervals | O(n log n) | O(n) | Dominated by the sort |
| Insert Interval | O(n) | O(n) | Already sorted input |
| Meeting Rooms (min rooms) | O(n log n) | O(n) | Sweep line or heap |
| Interval Scheduling Max | O(n log n) | O(1) | Greedy: sort by end time |
| Sweep Line | O(n log n) | O(n) | Sort events, scan once |
| Overlap Check (2 intervals) | O(1) | O(1) | a.start ≤ b.end && b.start ≤ a.end |
| Interval Intersections (2 lists) | O(n + m) | O(n + m) | Two-pointer merge |
| Weighted Job Scheduling | O(n log n) | O(n) | DP + binary search |
def merge(intervals):
"""Merge overlapping intervals.
Input: list of [start, end] pairs (unsorted).
Output: list of non-overlapping merged intervals.
Time: O(n log n) for sort + O(n) for merge = O(n log n)."""
if not intervals:
return []
# Sort by start time. If two intervals have the same start,
# the one with the larger end comes first (doesn't matter
# for correctness, but good to know).
intervals.sort(key=lambda x: x[0])
merged = [intervals[0][:]] # copy first interval
for start, end in intervals[1:]:
# Does this interval overlap with the last merged one?
if start <= merged[-1][1]:
# Yes: extend the end to cover both.
# IMPORTANT: use max(), not just assignment.
# [1,10] followed by [2,5] should stay [1,10], not [1,5].
merged[-1][1] = max(merged[-1][1], end)
else:
# No overlap: start a new group
merged.append([start, end])
return merged
# merge([[1,3],[2,6],[8,10],[15,18]]) → [[1,6],[8,10],[15,18]]
# merge([[1,4],[2,3]]) → [[1,4]] (containment case)
function merge(intervals) {
if (!intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]);
const merged = [[...intervals[0]]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
if (intervals[i][0] <= last[1]) {
// Overlap: extend end (use Math.max for containment case)
last[1] = Math.max(last[1], intervals[i][1]);
} else {
merged.push([...intervals[i]]);
}
}
return merged;
}
def min_meeting_rooms(intervals):
"""Find minimum number of meeting rooms needed.
Uses the sweep line technique: convert intervals to events,
sort, and track the running count of active meetings.
Time: O(n log n) for sort. Space: O(n) for events."""
if not intervals:
return 0
events = []
for start, end in intervals:
events.append((start, 1)) # +1: meeting starts
events.append((end, -1)) # -1: meeting ends
# Sort by time.
# Tie-breaker: ends (-1) before starts (+1).
# This means a room freed at time T is available for
# a meeting starting at time T. If the problem treats
# [1,5] and [5,10] as conflicting, reverse the tie-breaker.
events.sort()
max_rooms = current = 0
for _, delta in events:
current += delta
max_rooms = max(max_rooms, current)
return max_rooms
# min_meeting_rooms([[0,30],[5,10],[15,20]]) → 2
# min_meeting_rooms([[7,10],[2,4]]) → 1
import heapq
def min_meeting_rooms_heap(intervals):
"""Alternative: use a min-heap of end times.
The heap size at any point = rooms currently in use.
This approach is useful when you need to track WHICH
meetings are in which rooms, not just the count."""
if not intervals:
return 0
intervals.sort(key=lambda x: x[0]) # sort by start time
heap = [] # min-heap of meeting end times
for start, end in intervals:
# If the earliest-ending meeting is done before this one starts,
# reuse that room (pop its end time).
if heap and heap[0] <= start:
heapq.heappop(heap)
# Assign a room for this meeting
heapq.heappush(heap, end)
return len(heap) # heap size = max rooms needed
def insert(intervals, new):
"""Insert a new interval into a sorted, non-overlapping list.
Merges any overlapping intervals with the new one.
Three-phase approach:
1. Intervals entirely before the new one (no overlap)
2. Intervals that overlap with the new one (merge them)
3. Intervals entirely after the new one (no overlap)
Time: O(n), Space: O(n)."""
result = []
i, n = 0, len(intervals)
# Phase 1: add intervals that end before new starts
while i < n and intervals[i][1] < new[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge overlapping intervals with new
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]),
max(new[1], intervals[i][1])]
i += 1
result.append(new)
# Phase 3: add remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
# insert([[1,3],[6,9]], [2,5]) → [[1,5],[6,9]]
# insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]) → [[1,2],[3,10],[12,16]]
def max_non_overlapping(intervals):
"""Select maximum number of non-overlapping intervals.
Greedy: sort by END time, pick earliest-ending that doesn't conflict.
Equivalent formulation: "minimum intervals to REMOVE so the
rest don't overlap" = total - max_non_overlapping.
Time: O(n log n), Space: O(1) beyond sorting."""
if not intervals:
return 0
# Sort by end time — this is the key.
# Picking earliest end leaves most room for future intervals.
intervals.sort(key=lambda x: x[1])
count = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end: # no overlap with last picked
count += 1
last_end = end
return count
# Flip side: non_overlapping_intervals (min removals)
def erase_overlap_intervals(intervals):
"""Minimum number of intervals to remove so the rest don't overlap."""
return len(intervals) - max_non_overlapping(intervals)
def interval_intersection(A, B):
"""Find all overlapping segments between two sorted,
non-overlapping interval lists.
Two-pointer approach: advance the pointer whose current
interval ends first (it can't overlap with anything else
in the other list).
Time: O(n + m), Space: O(n + m) for output."""
result = []
i = j = 0
while i < len(A) and j < len(B):
# Find the overlap (if any)
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
result.append([lo, hi])
# Advance the pointer with the smaller end
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
# A = [[0,2],[5,10],[13,23],[24,25]]
# B = [[1,5],[8,12],[15,24],[25,26]]
# Result: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
from bisect import bisect_right
def job_scheduling(start, end, profit):
"""Maximum profit from non-overlapping jobs.
Each job i has start[i], end[i], profit[i].
Sort by end time. dp[i] = max profit considering first i jobs.
For each job, either skip it (dp[i-1]) or take it
(profit[i] + dp[last non-conflicting job]).
Binary search finds the last non-conflicting job efficiently.
Time: O(n log n), Space: O(n)."""
n = len(start)
jobs = sorted(zip(start, end, profit), key=lambda x: x[1])
ends = [j[1] for j in jobs]
dp = [0] * (n + 1)
for i in range(1, n + 1):
s, e, p = jobs[i - 1]
# Find last job that ends <= this job's start
# bisect_right gives insertion point for s in ends
k = bisect_right(ends, s, 0, i - 1)
# Option 1: skip this job (dp[i-1])
# Option 2: take this job (p + dp[k])
dp[i] = max(dp[i - 1], p + dp[k])
return dp[n]
# start = [1, 2, 3, 3]
# end = [3, 4, 5, 6]
# profit = [50,10,40,70]
# Answer: 120 (jobs 1 and 4: profit 50+70)
Given multiple people's calendars, find time slots where everyone is free — the classic meeting scheduling problem. This is exactly what Google Calendar's "Find a time" feature does.
def find_free_time(calendars, work_start=9*60, work_end=17*60):
"""Find common free time across multiple people's calendars.
calendars: list of lists, where each inner list contains
[start_min, end_min] intervals (minutes from midnight).
work_start/work_end: working hours in minutes (9am=540, 5pm=1020).
Algorithm:
1. Flatten all busy intervals from all calendars
2. Merge overlapping busy intervals
3. Find gaps between merged intervals within working hours
Returns list of [start, end] free slots."""
# Step 1: Flatten all busy times
all_busy = []
for person_cal in calendars:
all_busy.extend(person_cal)
if not all_busy:
return [[work_start, work_end]]
# Step 2: Merge overlapping busy intervals
all_busy.sort()
merged = [all_busy[0][:]]
for start, end in all_busy[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
# Step 3: Find gaps within working hours
free = []
prev_end = work_start
for busy_start, busy_end in merged:
# Clip to working hours
busy_start = max(busy_start, work_start)
busy_end = min(busy_end, work_end)
if busy_start > prev_end:
free.append([prev_end, busy_start])
prev_end = max(prev_end, busy_end)
if prev_end < work_end:
free.append([prev_end, work_end])
return free
def minutes_to_time(m):
return f"{m // 60}:{m % 60:02d}"
# Example: 3 people's calendars (times in minutes from midnight)
alice = [[540, 600], [660, 720]] # 9:00-10:00, 11:00-12:00
bob = [[570, 630], [780, 840]] # 9:30-10:30, 1:00-2:00
charlie = [[600, 660], [900, 960]] # 10:00-11:00, 3:00-4:00
free = find_free_time([alice, bob, charlie])
for slot in free:
print(f" {minutes_to_time(slot[0])} - {minutes_to_time(slot[1])}")
# Output:
# 10:30 - 11:00
# 12:00 - 13:00
# 14:00 - 15:00
# 16:00 - 17:00
| # | Problem | Difficulty | Key Concept |
|---|---|---|---|
| 56 | Merge Intervals | Medium | Sort + merge |
| 57 | Insert Interval | Medium | Three-phase insert |
| 252 | Meeting Rooms | Easy | Overlap check |
| 253 | Meeting Rooms II | Medium | Sweep line / min heap |
| 435 | Non-overlapping Intervals | Medium | Greedy scheduling |
| 986 | Interval List Intersections | Medium | Two-pointer merge |
| 1235 | Maximum Profit in Job Scheduling | Hard | DP + binary search |
| 759 | Employee Free Time | Hard | Merge + find gaps |
| 1094 | Car Pooling | Medium | Sweep line / difference array |