CODING PATTERNS · LESSON 4 OF 28 · 32 MIN VIDEO · 10 PROBLEMS

Intervals

Module Progress (0 / 10 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (32 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Intervals — How the Pattern Works

The Intervals pattern processes collections of [start, end] ranges by sorting them by start coordinate (or decomposing ranges into boundary events) and sweeping from left to right in a single pass. Sorting establishes the monotonic invariant intervals[i][0] <= intervals[i + 1][0], guaranteeing that all ranges overlapping the active span appear consecutively and only need comparison against the furthest active end seen so far (or a min-heap of active end times). This eliminates O(n^2) pairwise overlap checks and coordinate-dependent O(T) timeline scans, solving merge, gap, containment, and concurrency problems in O(n log n) time (or O(n) when pre-sorted).

WHEN TO USE THIS PATTERN
  • Input consists of [start, end] pairs representing meetings, schedules, reservations, trips, or numeric ranges.
  • Prompt asks to merge overlapping intervals, insert a range into sorted disjoint intervals, or remove covered/nested intervals.
  • Prompt asks to find shared intersections, common free time across schedules, or uncovered gaps within a bounded timeline.
  • Prompt asks for peak concurrency or resource capacity (minimum meeting rooms, vehicle seat capacity across overlapping trips).
  • Prompt asks to answer offline point-containment queries over ranges or maintain disjoint intervals dynamically from an integer stream.
COMMON INTERVIEW PITFALLS
  • Comparing the next interval's start against the previous interval's raw end instead of max_end so far — a nested short interval like [2, 3] inside [1, 5] shrinks the tracked boundary and misses subsequent overlaps such as [4, 8].
  • Off-by-one boundary semantics when end == next_start: closed-interval merging treats touching endpoints as overlapping (start <= end), whereas room reuse and passenger drop-offs free capacity at end <= start (requiring -delta drop-off events to sort before +delta pickups at identical coordinates).
  • Breaking start-time ties in ascending rather than descending end order for containment problems: given [1, 4] and [1, 6], sorting [1, 4] first fails to detect that [1, 6] covers [1, 4]; always sort with key=lambda x: (x[0], -x[1]).
  • Allocating timeline arrays of size O(max_end) instead of sweeping sorted interval endpoints in O(n log n), triggering memory or time limit failures when coordinates reach 10^9.
Sort-and-Sweep MergeCombine overlapping [start, end] intervals or detect gaps between covered stretches by tracking the furthest active end.
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged
Min-Heap of Active End TimesTrack concurrent intervals to compute minimum required rooms/resources or lazily evict expired intervals during a sweep.
import heapq

def min_resources(intervals):
    intervals.sort(key=lambda x: x[0])
    ends = []
    for start, end in intervals:
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)
Line-Sweep Endpoint EventsTrack weighted capacity or concurrent load across intervals by converting each range into +delta and -delta boundary events.
def within_capacity(trips, capacity):
    events = []
    for weight, start, end in trips:
        events.append((start, weight))
        events.append((end, -weight))
    load = 0
    for _, delta in sorted(events):
        load += delta
        if load > capacity:
            return False
    return True
🔒 PRO PROBLEMTarget: O(n + m) time · O(1) extra space

03. Interval List Intersections

Pattern Trigger: two sorted range lists → i and j, drop earlier end

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Merge one to five, two to three, and four to eight. What do you get?