Interval Scheduling — O(n²) Blowup Led to 30s Timeouts

Interval scheduling appears in every operating system (process time slots), every calendar application (meeting conflict detection), and virtually every resource allocation problem. The three variants — maximise non-overlapping intervals, minimise rooms needed, merge overlapping intervals — are among the most frequently asked algorithmic interview problems at top companies.

All three have elegant O(n log n) greedy solutions, but the correctness argument for each is different. Maximum non-overlapping uses earliest deadline first with an exchange argument. Minimum rooms uses a priority queue sweep. Merge intervals is just careful iteration. Knowing all three and why each works — not just what to code — is what distinguishes thorough preparation.

Why Interval Scheduling Is a Greedy Trap

Interval scheduling is the problem of selecting the maximum number of non-overlapping intervals from a set, each defined by a start and end time. The core mechanic: given intervals (s_i, f_i), choose the largest subset where no two intervals overlap. The canonical greedy solution sorts by finish time and picks the earliest-finishing compatible interval — O(n log n) and optimal.

What matters in practice: the greedy algorithm works only when intervals are unweighted. Weighted interval scheduling requires dynamic programming — O(n²) naive, O(n log n) with binary search. The key property is compatibility: two intervals i and j overlap if s_i < f_j and s_j < f_i. The DP recurrence builds on the last compatible interval before each job, which is where the O(n²) blowup hides if you don't precompute.

Use interval scheduling whenever you need to maximize throughput under exclusive resource access — CPU scheduling, meeting room allocation, bandwidth reservation. It matters because the naive DP is deceptively expensive: 10,000 intervals can produce 100 million compatibility checks, turning a 10ms problem into a 30-second timeout in production.

Problem 1 — Maximum Non-Overlapping Intervals

Greedy insight: always pick the interval that finishes earliest. This leaves maximum room for future intervals.

def max_non_overlapping(intervals: list[tuple]) -> list[tuple]:
    """
    Returns maximum set of non-overlapping intervals.
    Greedy: sort by end time, always pick earliest finish.
    """
    intervals = sorted(intervals, key=lambda x: x[1])
    selected = []
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:  # no overlap
            selected.append((start, end))
            last_end = end
    return selected

intervals = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
result = max_non_overlapping(intervals)
print(f'Max non-overlapping: {len(result)} → {result}')

Problem 2 — Minimum Meeting Rooms

Use a min-heap tracking end times of active meetings. For each meeting start, if the earliest-ending active meeting has ended, reuse its room.

import heapq

def min_meeting_rooms(intervals: list[tuple]) -> int:
    if not intervals:
        return 0
    intervals = sorted(intervals, key=lambda x: x[0])
    heap = []  # end times of active meetings
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse room
        else:
            heapq.heappush(heap, end)     # new room needed
    return len(heap)

print(min_meeting_rooms([(0,30),(5,10),(15,20)]))  # 2
print(min_meeting_rooms([(7,10),(2,4)]))             # 1

Problem 3 — Merge Overlapping Intervals

Sort by start time, merge consecutive overlapping intervals.

def merge_intervals(intervals: list[tuple]) -> list[tuple]:
    if not intervals:
        return []
    intervals = sorted(intervals, key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:           # overlapping
            merged[-1] = (merged[-1][0], max(merged[-1][1], end))
        else:
            merged.append((start, end))
    return merged

print(merge_intervals([(1,3),(2,6),(8,10),(15,18)]))  # [(1,6),(8,10),(15,18)]
print(merge_intervals([(1,4),(4,5)]))                  # [(1,5)]

Why Earliest Finish Time is Optimal

Claim: picking the interval with the earliest finish time is always in some optimal solution. Proof: suppose optimal starts with interval A instead of E (earliest finish). Replace A with E — since E finishes earlier, this can only improve future compatibility. By induction, greedy is optimal.

When Greedy Fails — Weighted Interval Scheduling

The earliest finish time greedy does NOT work when intervals have weights (values). A short, high-value interval might be later than a long, low-value one. For weighted interval scheduling you need dynamic programming: 1. Sort by end time 2. Use DP[i] = max(weight[i] + DP[p(i)], DP[i-1]) where p(i) is the last interval non-overlapping with i. This is O(n log n) with binary search for p(i).

def weighted_interval_scheduling(intervals: list[tuple]) -> int:
    # intervals: list of (start, end, weight)
    intervals = sorted(intervals, key=lambda x: x[1])  # sort by end
    n = len(intervals)
    # binary search for last non-overlapping interval
    def last_non_overlap(i):
        lo, hi = 0, i - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if intervals[mid][1] <= intervals[i][0]:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi
    dp = [0] * n
    dp[0] = intervals[0][2]
    for i in range(1, n):
        include = intervals[i][2]
        j = last_non_overlap(i)
        if j != -1:
            include += dp[j]
        dp[i] = max(include, dp[i-1])
    return dp[-1]

Common Techniques — Because Sorting Isn't a Personality

Interval problems look cute until you're three hours into a bug where your merge logic misses an edge case. The truth is there are maybe four patterns that cover 90% of what you'll see. Memorize them, don't worship them.

Sorting is the obvious one. You sort by start time when you need to chain intervals forward — merging, room counting, overlap detection. You sort by end time when you want to maximize count (earliest finish wins). If you don't know which axis to sort on, you haven't understood the problem's constraint.

Sweep line is the nuclear option. You flatten every interval into start/end events, then walk the timeline tallying active intervals. It's overkill for simple merge, but it's the only sane way to find peak overlap or handle point queries.

Prefix sums and segment trees? Those are for when your intervals aren't cheap O(n log n) sorted scans. If you're reaching for a segment tree in an interview, you better be solving range queries over mutable intervals, not a glorified calendar merge. Don't confuse sophistication with necessity.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class SweepLineOverlap {
    // Find maximum overlapping intervals at any point
    public static int maxOverlap(int[][] intervals) {
        List<int[]> events = new ArrayList<>();
        for (int[] iv : intervals) {
            events.add(new int[]{iv[0], 1});  // start
            events.add(new int[]{iv[1], -1}); // end
        }
        events.sort((a, b) -> a[0] != b[0] 
            ? Integer.compare(a[0], b[0]) 
            : Integer.compare(a[1], b[1]));
        
        int active = 0, maxCount = 0;
        for (int[] e : events) {
            active += e[1];
            maxCount = Math.max(maxCount, active);
        }
        return maxCount;
    }

    public static void main(String[] args) {
        int[][] meetings = {{1,5}, {2,6}, {3,7}, {4,8}};
        System.out.println(maxOverlap(meetings));
    }
}

Identifying Problems Involving Interval Manipulation — Read the Tell

Most interval problems announce themselves with specific language. If you hear "meetings," "appointments," "schedules," or "time slots," you're in interval territory. But the real giveaway is the operation: merge, count, find free time, or calculate duration of overlap.

There's a subtler pattern too. Any problem that gives you pairs of numbers and asks for something about "non-overlapping" or "maximum set" is almost certainly an interval scheduling variant. The moment you see a conflict detection between two ranges, stop pretending it's a geometry problem and sort the damn intervals.

What trips up juniors is disguised intervals. A problem might hand you server start times and durations — you need to compute end times yourself. Or it gives you string timestamps and wants the busiest hour. That's still intervals, just wrapped in parsing. Don't fall for the dressing. Strip it down to [start, end) and apply your tools.

If you find yourself writing three nested loops to compare every interval pair with every other — stop. You missed the pattern. Go back to the problem statement. Look for the operation keyword. Then sort, greedy, or sweep line. That's your playbook.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class DisguisedIntervals {
    // Servers start at given times, run for given durations.
    // Find the minute with most servers running.
    public static int peakServerLoad(int[] startTime, int[] duration) {
        int n = startTime.length;
        int[][] intervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            intervals[i][0] = startTime[i];
            intervals[i][1] = startTime[i] + duration[i];
        }
        // Now it's clearly an interval problem — sweep line
        List<int[]> events = new ArrayList<>();
        for (int[] iv : intervals) {
            events.add(new int[]{iv[0], 1});
            events.add(new int[]{iv[1], -1});
        }
        events.sort((a, b) -> a[0] != b[0] 
            ? Integer.compare(a[0], b[0]) 
            : Integer.compare(a[1], b[1]));
        
        int active = 0, peak = 0;
        for (int[] e : events) {
            active += e[1];
            peak = Math.max(peak, active);
        }
        return peak;
    }

    public static void main(String[] args) {
        int[] starts = {0, 2, 5};
        int[] durations = {10, 3, 5};
        System.out.println(peakServerLoad(starts, durations));
    }
}