DSA · Lesson 16 of 17

Greedy & Intervals

⏱ 14 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 4 practice problems

Make the locally best choice and prove it never hurts. Interval scheduling, merging, jump game and gas station, with the exchange-argument intuition.

The idea

A greedy algorithm makes the choice that looks best right now and never reconsiders. It is fast (often one sort plus one pass), but it is only correct when you can argue that the greedy choice is part of some optimal solution. The usual argument is an exchange argument: if an optimal solution made a different choice, swapping in the greedy one is no worse.

When you cannot find such an argument, or a small counterexample breaks it, use DP.

Interval problems: sort first

Problem	Sort by	Rule
Merge intervals	start	extend the last merged interval while `start ≤ lastEnd`
Non-overlapping intervals (max kept)	end	keep an interval if it starts after the last kept end
Meeting rooms II (min rooms)	start (+ min-heap of ends)	reuse the room that frees up first
Insert interval	already sorted	before / overlapping / after
Minimum arrows to burst balloons	end	shoot at the end of the first; skip all it pierces

Sorting by end time is the classic activity-selection greedy: finishing early leaves the most room for everything else.

Other greedy classics

Jump game: track the furthest reachable index.
Gas station: if the tank drops below zero at station i, no start between the current start and i works, so restart at i + 1.
Kadane’s algorithm: drop a negative running sum.
Assign cookies / boats to save people: sort both sides and match with two pointers.

Code template

def merge(intervals):
    intervals.sort()                         # by start
    res = []
    for s, e in intervals:
        if res and s <= res[-1][1]:
            res[-1][1] = max(res[-1][1], e)
        else:
            res.append([s, e])
    return res

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])       # by end
    count, end = 0, float('-inf')
    for s, e in intervals:
        if s >= end:
            count += 1; end = e
    return count

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));     // by start
    List<int[]> res = new ArrayList<>();
    for (int[] iv : intervals) {
        if (!res.isEmpty() && iv[0] <= res.get(res.size() - 1)[1]) res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], iv[1]);
        else res.add(new int[]{iv[0], iv[1]});
    }
    return res.toArray(new int[0][]);
}

int maxNonOverlapping(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));     // by end
    int count = 0; long end = Long.MIN_VALUE;
    for (int[] iv : intervals) if (iv[0] >= end) { count++; end = iv[1]; }
    return count;
}

vector<vector<int>> merge(vector<vector<int>> intervals) {
    sort(intervals.begin(), intervals.end());                          // by start
    vector<vector<int>> res;
    for (auto& iv : intervals) {
        if (!res.empty() && iv[0] <= res.back()[1]) res.back()[1] = max(res.back()[1], iv[1]);
        else res.push_back(iv);
    }
    return res;
}

int maxNonOverlapping(vector<vector<int>> intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[1] < b[1]; });   // by end
    int count = 0; long long end = LLONG_MIN;
    for (auto& iv : intervals) if (iv[0] >= end) { count++; end = iv[1]; }
    return count;
}

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);     // by start
  const res = [];
  for (const [s, e] of intervals) {
    if (res.length && s <= res[res.length - 1][1]) res[res.length - 1][1] = Math.max(res[res.length - 1][1], e);
    else res.push([s, e]);
  }
  return res;
}

function maxNonOverlapping(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);     // by end
  let count = 0, end = -Infinity;
  for (const [s, e] of intervals) if (s >= end) { count++; end = e; }
  return count;
}

Practise this pattern (4 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
83	Jump Game	Medium
84	Non-overlapping Intervals	Medium
85	Insert Interval	Medium
86	Gas Station	Medium

Common mistakes

Sorting by start when the problem needs end (or the reverse). Test both on a tiny example.
Treating touching intervals inconsistently: is [1,2] with [2,3] an overlap? Read the problem.
Using greedy for coin change with arbitrary coins (fails for [1, 3, 4] with amount 6).

Check yourself: why sort by end time for Non-overlapping Intervals?

The interval that ends first leaves the most room for the remaining ones. Any optimal solution can swap its first interval for the earliest-ending one without creating an overlap.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar