Intervals

Back to DSA & Algorithms/00 - Roadmap Overview

What are Interval Problems?

Interval problems deal with ranges [start, end]. They show up as meetings, time ranges, segments, etc. The universal first step: sort the intervals.

Key Concept: Overlap Detection

Two intervals [a, b] and [c, d] overlap when:

a ──────── b
      c ──────── d
      
Overlap: a < d AND c < b (each starts before the other ends)
No overlap: a >= d OR c >= b

Pattern 1: Merge Overlapping

Sort by start. Walk through and merge when current interval overlaps with previous.

java
public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0]);

    for (int i = 1; i < intervals.length; i++) {
        int start = intervals[i][0], end = intervals[i][1];
        int[] last = merged.get(merged.size() - 1);

        if (start <= last[1]) {
            // Overlaps with last merged interval → extend it
            last[1] = Math.max(last[1], end);
        } else {
            // No overlap → start new interval
            merged.add(new int[]{start, end});
        }
    }

    return merged.toArray(new int[merged.size()][]);
}

// [[1,3],[2,6],[8,10],[15,18]]
// Sorted: same (already sorted by start)
// [1,3]: merged = 1,3
// [2,6]: 2 <= 3 → merge → 1,6
// [8,10]: 8 > 6 → new → [[1,6],[8,10]]
// [15,18]: 15 > 10 → new → [[1,6],[8,10],[15,18]]

Insert Interval

java
public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0;
    int n = intervals.length;

    // Add all intervals that END before new starts
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]);
        i++;
    }

    // Merge all overlapping intervals with new
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval = new int[]{
            Math.min(newInterval[0], intervals[i][0]),
            Math.max(newInterval[1], intervals[i][1])
        };
        i++;
    }
    result.add(newInterval);

    // Add remaining intervals
    while (i < n) {
        result.add(intervals[i]);
        i++;
    }

    return result.toArray(new int[result.size()][]);
}

Problems

Pattern 2: Sweep Line (Event-Based)

What it is

Convert intervals into start/end events, sort them, and process in order. Track how many intervals are "active" at each point.

The Mental Model

Imagine a hotel. Guests check in (start event, +1) and check out (end event, -1). Walk through the day tracking the current number of guests. The maximum at any point = minimum rooms needed.

java
public int minMeetingRooms(int[][] intervals) {
    List<int[]> events = new ArrayList<>();
    for (int[] interval : intervals) {
        events.add(new int[]{interval[0], 1});    // Meeting starts
        events.add(new int[]{interval[1], -1});   // Meeting ends
    }

    // Sort by time, then by type (-1 before +1 at same time)
    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));

    int rooms = 0;
    int maxRooms = 0;
    for (int[] event : events) {
        rooms += event[1];
        maxRooms = Math.max(maxRooms, rooms);
    }

    return maxRooms;
}

// Note: at the same time, end events (-1) should come before start events (+1).
// This handles the case where one meeting ends at 10:00 and another starts at 10:00
// → they can share the room.
// Sorting (time, delta) handles this naturally since -1 < 1.

Problems

Pattern 3: Interval Intersection

Two pointers, one per list of sorted intervals.

java
public int[][] intervalIntersection(int[][] A, int[][] B) {
    List<int[]> result = new ArrayList<>();
    int i = 0, j = 0;

    while (i < A.length && j < B.length) {
        int lo = Math.max(A[i][0], B[j][0]);   // Intersection starts at the later start
        int hi = Math.min(A[i][1], B[j][1]);   // Intersection ends at the earlier end

        if (lo <= hi) {
            result.add(new int[]{lo, hi});      // Valid intersection
        }

        // Advance the pointer whose interval ends first
        if (A[i][1] < B[j][1]) {
            i++;
        } else {
            j++;
        }
    }

    return result.toArray(new int[result.size()][]);
}

Problems

Things to Be Aware Of

1. Sort Criterion Matters

Merge overlapping → sort by START
Select max non-overlapping → sort by END
Each gives different results and serves different purposes.

2. Inclusive vs Exclusive Boundaries

[1, 5] and [5, 10]: Do they overlap?
If boundaries are inclusive: YES (they touch at 5)
If end is exclusive: NO ([1,5) and [5,10) don't share any point)
Always check the problem's convention.