Learn DSA Part 12: Greedy Algorithms - Intervals, Jump Game, Gas Station and Proofs

A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now and never going back. When it works, it gives short, fast solutions, often just "sort, then one pass". The hard part is knowing when greedy is correct, because a greedy idea that looks right can fail on a single tricky input.

This is Part 12 of the Learn DSA series. We cover when greedy works, the interval-scheduling family, reach-based problems like Jump Game, the gas station trick, and how to convince yourself (and an interviewer) that a greedy choice is safe. Code is in C++ and Java.

1. When does greedy work?

Greedy is correct when a problem has two properties:

• Greedy choice property: some locally best choice is always part of an optimal solution.
• Optimal substructure: after making that choice, what remains is a smaller instance of the same problem.

A classic failure is making change with coins {1, 3, 4} for amount 6. Greedy takes 4 + 1 + 1 (three coins), but 3 + 3 uses only two. With standard currency like {1, 2, 5, 10} greedy happens to work, but for arbitrary coins you need dynamic programming (Part 13). Always test a greedy idea on small tricky cases before coding it.

2. Pattern 1: interval scheduling

Many interval problems become greedy after sorting. To keep the maximum number of non-overlapping intervals, sort by end time and repeatedly take the interval that ends earliest; finishing early leaves the most room for the rest.

// Minimum intervals to remove so the rest do not overlap. O(n log n)
int eraseOverlapIntervals(vector<vector<int>>& iv) {
    sort(iv.begin(), iv.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
    int kept = 0;
    long long lastEnd = LLONG_MIN;
    for (auto& x : iv) {
        if (x[0] >= lastEnd) { kept++; lastEnd = x[1]; }  // take earliest end
    }
    return (int)iv.size() - kept;
}

// Minimum intervals to remove so the rest do not overlap. O(n log n)
static int eraseOverlapIntervals(int[][] iv) {
    Arrays.sort(iv, (a, b) -> Integer.compare(a[1], b[1]));
    int kept = 0;
    long lastEnd = Long.MIN_VALUE;
    for (int[] x : iv) {
        if (x[0] >= lastEnd) { kept++; lastEnd = x[1]; }  // take earliest end
    }
    return iv.length - kept;
}

• Merge Intervals: sort by start, then extend the current interval while the next one overlaps.
• Minimum Number of Arrows to Burst Balloons: the same "sort by end" logic as above.
• Meeting Rooms II: sort by start and track end times with a min-heap (Part 10).

3. Pattern 2: reach and jumps

In Jump Game you may jump up to nums[i] steps from index i. Instead of trying every path, track the farthest index reachable so far. If you ever stand at an index beyond that reach, the end is unreachable.

For the minimum number of jumps (Jump Game II), think of it as BFS by levels without a queue: all indices reachable with k jumps form one level, and the next level ends at the farthest point reachable from it.

// Jump Game II: minimum jumps to reach the last index. O(n)
int jump(const vector<int>& nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        farthest = max(farthest, i + nums[i]);
        if (i == curEnd) {          // finished the current level
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}

// Jump Game II: minimum jumps to reach the last index. O(n)
static int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i + 1 < nums.length; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {          // finished the current level
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}

Both run in O(n) time and O(1) space, compared with O(n^2) for a DP that checks every earlier position.

4. Pattern 3: running balance (Gas Station)

In Gas Station, you start with an empty tank at some station, gain gas[i] and spend cost[i] to reach the next one. Two observations give an O(n) solution:

1. If total gas is less than total cost, no start works.
2. If you start at s and run out before station j, then no station between s and j can be a valid start either, so restart at j + 1.

// Gas Station: starting index to complete the circuit, or -1. O(n)
int canCompleteCircuit(const vector<int>& gas, const vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < (int)gas.size(); i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) { start = i + 1; tank = 0; }   // restart after i
    }
    return total >= 0 ? start : -1;
}

// Gas Station: starting index to complete the circuit, or -1. O(n)
static int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) { start = i + 1; tank = 0; }   // restart after i
    }
    return total >= 0 ? start : -1;
}

The same "reset when the running value goes negative" idea appears in Kadane's algorithm (Part 2) and the Best Time to Buy and Sell Stock problems.

5. Pattern 4: sort, then match greedily

• Assign Cookies: sort children's greed and cookie sizes, and give each child the smallest cookie that satisfies them.
• Boats to Save People: sort weights and pair the heaviest remaining person with the lightest if they fit (two pointers, Part 4).
• Partition Labels: record the last occurrence of each letter, then extend the current part until you reach the furthest last occurrence seen.
• Task Scheduler and Reorganize String: always schedule the most frequent remaining item (a max-heap).
• Huffman coding: repeatedly merge the two least frequent symbols, also with a min-heap.

6. How to justify a greedy choice

Interviewers often ask "why does this work?". The standard argument is an exchange argument: take any optimal solution that does not make your greedy choice, and show you can swap in the greedy choice without making the solution worse. For interval scheduling: if an optimal plan starts with some interval, replacing it with the interval that ends earliest cannot cause new overlaps, so an optimal plan exists that agrees with greedy.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. Before coding, write down your greedy rule and try to break it with a small example.

1. Assign Cookies (easy)
2. Lemonade Change (easy)
3. Best Time to Buy and Sell Stock II (medium)
4. Jump Game (medium)
5. Jump Game II (medium)
6. Gas Station (medium)
7. Non-overlapping Intervals (medium)
8. Minimum Number of Arrows to Burst Balloons (medium)
9. Merge Intervals (medium)
10. Partition Labels (medium)
11. Boats to Save People (medium)
12. Task Scheduler (medium)
13. Candy (hard)