Intervals and greedy
Coding interviews

Intervals & greedy

Merge intervals, meeting rooms, sweep lines, and greedy picks — plus when greedy lies — with plain-language explanation before templates.

Pooja Singh 9 min read ·

Sort first

Almost every interval problem starts by sorting on start (or end). Merge scans once. Greedy works when a local rule never blocks a better global solution — if you can’t argue that, consider DP.

Analogy: calendar merge

Interval calendar
Overlapping meetings collapse into one block.

Intervals are calendar blocks. Merge = if two meetings overlap on your calendar, combine them into one busy block. Greedy “earliest end first” = always protect the meeting that frees the room soonest so you can fit more later.

Intervals

Intervals
Sort, merge, sweep.
def merge(intervals):
    intervals.sort()
    out = []
    for s,e in intervals:
        if not out or out[-1][1] < s: out.append([s,e])
        else: out[-1][1] = max(out[-1][1], e)
    return out
List<int[]> merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> out = new ArrayList<>();
    for (int[] iv : intervals) {
        if (out.isEmpty() || out.get(out.size() - 1)[1] < iv[0]) out.add(new int[]{iv[0], iv[1]});
        else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], iv[1]);
    }
    return out;
}

Greedy

Greedy checklist
Choice · proof · counterexample.

Drill list

  1. Merge intervals
  2. Insert interval
  3. Meeting rooms II (heap/sweep)
  4. Non-overlapping intervals
  5. Jump game I/II
  6. Gas station
  7. Partition labels

When to reach for this pattern

Intervals almost always start with sort. Greedy always needs one sentence of justification — interviewers accept short proofs, not vibes.

Core template + worked trace

Merge intervals:

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort()  # by start
    out = []
    for s, e in intervals:
        if not out or out[-1][1] < s:
            out.append([s, e])
        else:
            out[-1][1] = max(out[-1][1], e)
    return out

# [[1,3],[2,6],[8,10]] → [[1,6],[8,10]]
# 1–3 absorbs 2–6 because 3 >= 2; 8>6 so new interval
List<int[]> merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));  // by start
    List<int[]> out = new ArrayList<>();
    for (int[] iv : intervals) {
        int s = iv[0], e = iv[1];
        if (out.isEmpty() || out.get(out.size() - 1)[1] < s) {
            out.add(new int[]{s, e});
        } else {
            out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], e);
        }
    }
    return out;
}

// [[1,3],[2,6],[8,10]] → [[1,6],[8,10]]
// 1–3 absorbs 2–6 because 3 >= 2; 8>6 so new interval

Greedy jump game — track farthest reach:

def can_jump(nums: list[int]) -> bool:
    far = 0
    for i, step in enumerate(nums):
        if i > far:
            return False
        far = max(far, i + step)
        if far >= len(nums) - 1:
            return True
    return True

# [2,3,1,1,4]: far grows 0→2→4 → reachable
# [3,2,1,0,4]: stuck at far=3 when i=4
boolean canJump(int[] nums) {
    int far = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > far) return false;
        far = Math.max(far, i + nums[i]);
        if (far >= nums.length - 1) return true;
    }
    return true;
}

// [2,3,1,1,4]: far grows 0→2→4 → reachable
// [3,2,1,0,4]: stuck at far=3 when i=4

Edge cases & common bugs

Complexity — say it aloud

Interview talk track

You: ‘I’ll sort by start and merge when the next start is ≤ current end. For jump game I’ll track the farthest index reachable so far — if I ever stand beyond that, I’m stuck.’

Practice set

  • Merge Intervals
  • Insert Interval
  • Non-overlapping Intervals
  • Meeting Rooms / Meeting Rooms II
  • Jump Game / Jump Game II
  • Gas Station
  • Candy (greedy stretch)
  • Minimum Number of Arrows to Burst Balloons

Harder follow-up

Harder variant: Non-overlapping Intervals — erase minimum intervals. Sort by end; greedily keep an interval if it starts after the last kept end. Proof: earliest finish leaves more room.

Pattern bank: more questions + efficient solutions

Five high-frequency interval / greedy questions. Sort first, then one linear scan — say that before coding.

Q: Merge Intervals — given intervals [start, end], merge all overlapping and return non-overlapping sorted intervals.
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = []
    for s, e in intervals:
        if not out or s > out[-1][1]:
            out.append([s, e])
        else:
            out[-1][1] = max(out[-1][1], e)
    return out
# O(n log n) sort + O(n) merge
List<int[]> merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> out = new ArrayList<>();
    for (int[] cur : intervals) {
        if (out.isEmpty() || cur[0] > out.get(out.size() - 1)[1]) out.add(cur.clone());
        else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], cur[1]);
    }
    return out; // O(n log n)
}
Q: Insert Interval — insert newInterval into a sorted non-overlapping list and merge if needed.
def insert(intervals, new):
    res, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:
        res.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1]); i += 1
    res.append(new)
    while i < n:
        res.append(intervals[i]); i += 1
    return res
List<int[]> insert(int[][] intervals, int[] neu) {
    List<int[]> res = new ArrayList<>();
    int i = 0, n = intervals.length;
    while (i < n && intervals[i][1] < neu[0]) res.add(intervals[i++]);
    while (i < n && intervals[i][0] <= neu[1]) {
        neu[0] = Math.min(neu[0], intervals[i][0]);
        neu[1] = Math.max(neu[1], intervals[i][1]); i++;
    }
    res.add(neu);
    while (i < n) res.add(intervals[i++]);
    return res; // O(n)
}
Q: Non-overlapping Intervals — erase the minimum number of intervals so the rest are non-overlapping.
def erase_overlap(intervals):
    intervals.sort(key=lambda x: x[1])
    kept, end = 0, float("-inf")
    for s, e in intervals:
        if s >= end:
            kept += 1; end = e
    return len(intervals) - kept
int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
    int kept = 0, end = Integer.MIN_VALUE;
    for (int[] it : intervals) {
        if (it[0] >= end) { kept++; end = it[1]; }
    }
    return intervals.length - kept; // O(n log n)
}
Q: Jump Game II — minimum jumps to reach last index; nums[i] = max jump length from i. Guaranteed reachable.
def jump(nums):
    jumps = end = far = 0
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == end:
            jumps += 1; end = far
    return jumps
int jump(int[] nums) {
    int jumps = 0, end = 0, far = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        far = Math.max(far, i + nums[i]);
        if (i == end) { jumps++; end = far; }
    }
    return jumps; // O(n)
}
Q: Gas Station — circular route; gas[i], cost[i]. Return start index or -1 if impossible.
def can_complete(gas, cost):
    if sum(gas) < sum(cost): return -1
    tank = start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1; tank = 0
    return start
int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        total += gas[i] - cost[i];
        tank += gas[i] - cost[i];
        if (tank < 0) { start = i + 1; tank = 0; }
    }
    return total < 0 ? -1 : start; // O(n)
}

45-minute pattern drill

codingintervalsgreedy

← Lattice