Greedy Algorithms and Interval Problems

You are at a shop counter and owe 94 rupees, and you want to hand over as few notes and coins as possible. What do you do? Almost everyone gives the largest note that fits, then the largest that fits into the remainder, and so on. That is a greedy approach: at each step, grab the best-looking choice, and never look back.

For the rupee, this method happens to give the fewest notes and coins. But does it always? What if the coin values were 1, 3 and 4, and you owed 6? Greedy hands over 4, then 1, then 1, which is three coins. But 3 and 3 is only two. The greedy rule that worked beautifully for one set of coins fails for another.

That is the core lesson of this article. Greedy is wonderfully simple, and sometimes wrong. The skill is not writing the loop. It is knowing when a greedy rule can be trusted, how to argue that it is correct, and how to catch it when it is not.

• What a greedy algorithm is, and what makes it correct.
• How to hunt for counterexamples, and how to test a greedy rule against brute force.
• The classic interval problems: activity selection, merging, and counting overlaps.
• Jump game, a greedy problem with a simple invariant.
• How to tell when greedy fails and a different method is needed.

A greedy algorithm builds a solution step by step. At each step it makes the locally best choice, according to some rule, and never undoes it. This is fast and easy to code, but a locally best choice can lock you out of the globally best answer.

A greedy rule is correct only if the problem has these two properties:

1. Greedy-choice property. Some optimal solution includes the greedy choice. In other words, taking the greedy choice first never costs you the best answer.
2. Optimal substructure. After you make the greedy choice, what remains is a smaller problem of the same kind, and an optimal solution to it combines with your choice to give an optimal solution overall.

You do not prove these formally in every interview, but you should be able to give a convincing argument. The most common argument is the exchange argument:

Take any optimal solution. If it does not use the greedy choice, swap one of its choices for the greedy one. Show that the result is still valid and no worse. So an optimal solution that includes the greedy choice exists.

Let us test the coin idea properly. Greedy for coins: take as many of the largest coin as fit, then move to the next largest.

To check whether it is right, we need something we know is right to compare with. For that we use a slower method that tries every possibility smartly (a taste of dynamic programming, which we meet in Dynamic Programming Foundations). It computes the best answer for every amount from 1 up to the target, using the best answers for smaller amounts.

// File: Main.javaimport java.util.Arrays;public class Main {    // Greedy: coins must be sorted from largest to smallest.    static int greedyCoins(int[] coinsDescending, int amount) {        int count = 0;        for (int coin : coinsDescending) {            count += amount / coin;            amount %= coin;        }        return amount == 0 ? count : -1;    }    // Always-correct (but slower to explain) method: best[a] = fewest coins to make amount a.    static int fewestCoins(int[] coins, int amount) {        int[] best = new int[amount + 1];        Arrays.fill(best, Integer.MAX_VALUE);        best[0] = 0;        for (int a = 1; a <= amount; a++) {            for (int coin : coins) {                if (coin <= a && best[a - coin] != Integer.MAX_VALUE) {                    best[a] = Math.min(best[a], best[a - coin] + 1);                }            }        }        return best[amount] == Integer.MAX_VALUE ? -1 : best[amount];    }    static void compare(String name, int[] coinsDescending, int limit) {        int mismatches = 0;        int firstMismatch = -1;        for (int amount = 1; amount <= limit; amount++) {            if (greedyCoins(coinsDescending, amount) != fewestCoins(coinsDescending, amount)) {                mismatches++;                if (firstMismatch == -1) {                    firstMismatch = amount;                }            }        }        System.out.println(name + ": greedy is wrong for " + mismatches + " of the amounts 1.." + limit                + (firstMismatch == -1 ? "" : " (first at " + firstMismatch + ")"));    }    public static void main(String[] args) {        int[] rupee = {500, 200, 100, 50, 20, 10, 5, 2, 1};        int[] odd = {4, 3, 1};        System.out.println("amount 6 with coins 4, 3, 1: greedy=" + greedyCoins(odd, 6) + " best=" + fewestCoins(odd, 6));        compare("coins 500,200,100,50,20,10,5,2,1", rupee, 3000);        compare("coins 4,3,1", odd, 100);    }}

amount 6 with coins 4, 3, 1: greedy=3 best=2coins 500,200,100,50,20,10,5,2,1: greedy is wrong for 0 of the amounts 1..3000coins 4,3,1: greedy is wrong for 24 of the amounts 1..100 (first at 6)

For the rupee-style denominations, greedy matched the always-correct method for every amount up to 3,000 that we tried. For {4, 3, 1} it fails, first at 6. So the method is not what decides correctness. The coin values are: some sets of coins (called canonical) have the greedy-choice property, and others do not. You cannot assume it. When a greedy rule is not valid, the fix is usually dynamic programming.

Most greedy problems follow the same shape:

1. Sort the items by a well-chosen key.
2. Scan once, taking an item whenever it is compatible with what you have already taken.

The whole difficulty is choosing the key. A wrong key gives wrong answers that still look reasonable on simple examples. The next problem shows this clearly.

Problem. You have a list of intervals, each with a start and an end (like meetings in one room). Two intervals conflict if they overlap, but one that ends exactly when another starts is fine. Choose the largest number of intervals so that none conflict.

There are several tempting rules:

Only one of these is correct. Look at why the others fail:

• Earliest start fails on [0, 100], [1, 2], [3, 4]. Earliest start takes [0, 100] first, which blocks everything else: 1 interval. The best choice is [1, 2] and [3, 4]: 2 intervals.
• Shortest first fails on [0, 5], [4, 6], [5, 10]. The shortest is [4, 6], which overlaps both of the others: 1 interval. But [0, 5] and [5, 10] fit together: 2 intervals.

Earliest end first works. Sort by end time. Take the first interval. Then, scanning on, take any interval whose start is at or after the end of the last one you took.

Let G be the interval with the earliest end overall. Take any optimal solution, and let X be its first interval (the one with the earliest end among its intervals). Since G ends no later than X does, replacing X with G cannot create a conflict with the other chosen intervals: they all start at or after X ends, which is at or after G ends. So the new set is still valid and the same size. Hence some optimal solution includes G. After taking G, the problem is the same question over the intervals that start at or after G ends, and we repeat the argument.

The following program compares the three rules against a brute force that tries every subset (fine for a handful of intervals). It runs on 2,000 random small cases and counts how often each rule gives a worse answer than the true best.

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Random;public class Main {    static int pick(int[][] sorted) {        int count = 0;        long lastEnd = Long.MIN_VALUE;        for (int[] interval : sorted) {            if (interval[0] >= lastEnd) {          // starts at or after the last chosen one ends                count++;                lastEnd = interval[1];            }        }        return count;    }    static int byEarliestEnd(int[][] intervals) {        int[][] s = intervals.clone();        Arrays.sort(s, (a, b) -> Integer.compare(a[1], b[1]));        return pick(s);    }    static int byEarliestStart(int[][] intervals) {        int[][] s = intervals.clone();        Arrays.sort(s, (a, b) -> Integer.compare(a[0], b[0]));        return pick(s);    }    static int byShortest(int[][] intervals) {        int[][] s = intervals.clone();        Arrays.sort(s, (a, b) -> Integer.compare(a[1] - a[0], b[1] - b[0]));   // safe here: small values        return pick(s);    }    // Tries every subset. Only for tiny inputs.    static int bruteForce(int[][] intervals) {        int n = intervals.length;        int best = 0;        for (int mask = 0; mask < (1 << n); mask++) {            List<int[]> chosen = new ArrayList<>();            for (int i = 0; i < n; i++) {                if ((mask & (1 << i)) != 0) {                    chosen.add(intervals[i]);                }            }            chosen.sort((a, b) -> Integer.compare(a[0], b[0]));            boolean ok = true;            for (int i = 1; i < chosen.size(); i++) {                if (chosen.get(i - 1)[1] > chosen.get(i)[0]) {                    ok = false;                    break;                }            }            if (ok) {                best = Math.max(best, chosen.size());            }        }        return best;    }    public static void main(String[] args) {        int[][] blocked = {{0, 100}, {1, 2}, {3, 4}};        int[][] crowded = {{0, 5}, {4, 6}, {5, 10}};        System.out.println("earliest start on " + "(0,100) (1,2) (3,4): " + byEarliestStart(blocked) + ", best is " + bruteForce(blocked));        System.out.println("shortest first on " + "(0,5) (4,6) (5,10): " + byShortest(crowded) + ", best is " + bruteForce(crowded));        Random random = new Random(1);        int wrongEnd = 0;        int wrongStart = 0;        int wrongShortest = 0;        int trials = 2000;        for (int t = 0; t < trials; t++) {            int n = 1 + random.nextInt(7);            int[][] intervals = new int[n][];            for (int i = 0; i < n; i++) {                int start = random.nextInt(10);                intervals[i] = new int[] {start, start + 1 + random.nextInt(5)};            }            int best = bruteForce(intervals);            if (byEarliestEnd(intervals) != best) {                wrongEnd++;            }            if (byEarliestStart(intervals) != best) {                wrongStart++;            }            if (byShortest(intervals) != best) {                wrongShortest++;            }        }        System.out.println("out of " + trials + " random cases, wrong answers: earliest end=" + wrongEnd                + ", earliest start=" + wrongStart + ", shortest=" + wrongShortest);    }}

earliest start on (0,100) (1,2) (3,4): 1, best is 2shortest first on (0,5) (4,6) (5,10): 1, best is 2out of 2000 random cases, wrong answers: earliest end=0, earliest start=242, shortest=916

In our run, the earliest-start rule gave a wrong answer in 242 of the 2,000 cases, the shortest-first rule in 916 of them, and the earliest-end rule in none. A rule that sounds sensible can fail close to half the time. This is exactly how to build trust in a greedy idea when you cannot find a proof in the moment: write a slow brute force and compare on thousands of small random inputs. It cannot prove correctness, but it finds almost every wrong rule within seconds. We used the fixed seed 1 so the result is repeatable.

Complexity of the greedy method: sorting is O(n log n) and the scan is O(n). Extra space is O(1) besides the sorted copy.

Problem. Merge all overlapping intervals into a minimal set of non-overlapping ones. [[1, 3], [2, 6], [8, 10], [15, 18]] becomes [[1, 6], [8, 10], [15, 18]].

Idea. Sort by start. Keep a current interval. For each next interval: if its start is at or before current's end, they overlap, so extend current's end to the larger of the two ends. Otherwise, current is finished: save it and begin a new one.

Notice the maximum. An interval can sit entirely inside the current one ([1, 10] and [2, 3]), in which case the end must not shrink to 3.

Whether intervals that only touch ([1, 4] and [4, 5]) merge is a policy that the problem states. Here, touching intervals merge, because we use <=.

Problem. Given the start and end times of meetings, find the minimum number of rooms so that no two meetings in the same room overlap. A meeting that ends at the same time another starts can reuse the room.

Idea. The answer is the maximum number of meetings happening at the same time. Sort the start times and the end times separately. Sweep through the starts in order. Before counting a new meeting, free up every room whose meeting has already ended (end time at or before this start). Then take a room, and record the maximum number of rooms in use.

You may recognise this as the sweep-line view of the difference array from the previous article: each start adds one to the "in use" count, and each end subtracts one.

Problem. An array nums says how far you can jump from each position: standing at i, you may jump to any position up to i + nums[i]. Starting at index 0, can you reach the last index?

Idea. Walk through the array while tracking furthest, the furthest index reachable so far. If you ever stand at an index i > furthest, you are stuck beyond reach, so the answer is false. Otherwise update furthest = max(furthest, i + nums[i]). If furthest reaches the end, the answer is true.

The invariant is "every index up to furthest is reachable". That holds because from any reachable index you can also reach all the indexes before its maximum reach, so reachable positions always form an unbroken stretch from 0.

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Main {    static int[][] merge(int[][] intervals) {        if (intervals.length == 0) {            return new int[0][];        }        int[][] sorted = intervals.clone();                // sorting reorders the copy, not the caller's array        Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));        List<int[]> result = new ArrayList<>();        int[] current = {sorted[0][0], sorted[0][1]};        for (int i = 1; i < sorted.length; i++) {            if (sorted[i][0] <= current[1]) {                current[1] = Math.max(current[1], sorted[i][1]);   // overlap: extend, never shrink            } else {                result.add(current);                current = new int[] {sorted[i][0], sorted[i][1]};            }        }        result.add(current);        return result.toArray(new int[0][]);    }    static int minMeetingRooms(int[][] meetings) {        int n = meetings.length;        int[] starts = new int[n];        int[] ends = new int[n];        for (int i = 0; i < n; i++) {            starts[i] = meetings[i][0];            ends[i] = meetings[i][1];        }        Arrays.sort(starts);        Arrays.sort(ends);        int rooms = 0;        int best = 0;        int e = 0;        for (int s = 0; s < n; s++) {            while (e < n && ends[e] <= starts[s]) {                e++;                rooms--;                                   // a meeting finished, its room is free            }            rooms++;            best = Math.max(best, rooms);        }        return best;    }    static boolean canJump(int[] nums) {        long furthest = 0;        for (int i = 0; i < nums.length; i++) {            if (i > furthest) {                return false;                              // stuck before reaching index i            }            furthest = Math.max(furthest, (long) i + nums[i]);            if (furthest >= nums.length - 1) {                return true;            }        }        return true;    }    static String show(int[][] intervals) {        StringBuilder sb = new StringBuilder();        for (int[] iv : intervals) {            sb.append('(').append(iv[0]).append(',').append(iv[1]).append(") ");        }        return sb.toString().trim();    }    public static void main(String[] args) {        System.out.println(show(merge(new int[][] {{1, 3}, {2, 6}, {8, 10}, {15, 18}})));        System.out.println(show(merge(new int[][] {{1, 4}, {4, 5}})));        System.out.println(show(merge(new int[][] {{1, 10}, {2, 3}})));        System.out.println(show(merge(new int[][] {{8, 10}, {1, 3}, {2, 6}})));        System.out.println("[" + show(merge(new int[][] {})) + "]");        System.out.println(minMeetingRooms(new int[][] {{0, 30}, {5, 10}, {15, 20}}) + " " + minMeetingRooms(new int[][] {{7, 10}, {2, 4}})                + " " + minMeetingRooms(new int[][] {{1, 5}, {5, 8}}) + " " + minMeetingRooms(new int[][] {}) + " " + minMeetingRooms(new int[][] {{1, 4}, {2, 5}, {3, 6}}));        System.out.println(canJump(new int[] {2, 3, 1, 1, 4}) + " " + canJump(new int[] {3, 2, 1, 0, 4}) + " " + canJump(new int[] {0}) + " " + canJump(new int[] {1, 0, 1}));    }}

(1,6) (8,10) (15,18)(1,5)(1,10)(1,6) (8,10)[]2 1 1 0 3true false true false

Dry run of merge on [[1, 3], [2, 6], [8, 10], [15, 18]] (already sorted by start):

Dry run of minMeetingRooms on [[0, 30], [5, 10], [15, 20]]: sorted starts 0, 5, 15, sorted ends 10, 20, 30.

The answer is 2: the first meeting runs the whole time, and the other two share a second room.

Complexity: merge and minMeetingRooms are O(n log n) for the sort, plus O(n) for the scan. canJump is O(n) time and O(1) space, with no sorting.

1. What are the choices? What does it mean to take one item?
2. What is the natural greedy rule? Often: sort by something and take items in that order.
3. Can you find a counterexample? Try 3 or 4 tiny cases that stress the rule: the first-looking choice being a trap, ties, nested items, huge items.
4. Can you justify it? Use an exchange argument, or a "stays ahead" argument: show that after each step, greedy is at least as good as any other strategy.
5. Can you test it? Compare against brute force on small random inputs.
6. If it fails, think dynamic programming (or backtracking with pruning, if the input is small).

• Trusting a greedy rule without a counterexample search. It is easy to be fooled by the first example.
• Sorting by the wrong key. End time for "most intervals", start time for "merge".
• Shrinking the end when merging. Use Math.max for nested intervals.
• Unclear touching semantics. Decide whether [1, 4] and [4, 5] overlap, and use < or <= consistently.
• Subtraction in a comparator, such as a[0] - b[0], which can overflow. Use Integer.compare. (We used a subtraction on interval lengths in one program above only because the numbers are tiny.)
• Sorting the caller's array when you should not. Copy first.
• Empty input. Return a sensible value (an empty list, 0).
• Using greedy for "all possibilities" questions. Greedy returns one answer, not every answer.
• Forgetting ties. If two items tie on the sort key, a different tie-break can change the result. Check whether it matters.

static int[][] mergeBuggy(int[][] intervals) {    int[][] sorted = intervals.clone();    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);    List<int[]> result = new ArrayList<>();    int[] current = sorted[0];    for (int i = 1; i < sorted.length; i++) {        if (sorted[i][0] <= current[1]) {            current[1] = sorted[i][1];        } else {            result.add(current);            current = sorted[i];        }    }    result.add(current);    return result.toArray(new int[0][]);}

// File: Main.javaimport java.util.Arrays;public class Main {    static int minRemovals(int[][] intervals) {        if (intervals.length == 0) {            return 0;        }        int[][] sorted = intervals.clone();        Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1]));        int kept = 0;        long lastEnd = Long.MIN_VALUE;        for (int[] iv : sorted) {            if (iv[0] >= lastEnd) {                kept++;                lastEnd = iv[1];            }        }        return intervals.length - kept;    }    public static void main(String[] args) {        System.out.println(minRemovals(new int[][] {{1, 2}, {2, 3}, {3, 4}, {1, 3}}));        System.out.println(minRemovals(new int[][] {{1, 2}, {1, 2}, {1, 2}}));        System.out.println(minRemovals(new int[][] {{1, 2}, {2, 3}}));        System.out.println(minRemovals(new int[][] {}));    }}

1200

// File: Main.javaimport java.util.Arrays;public class Main {    static int minArrows(int[][] balloons) {        if (balloons.length == 0) {            return 0;        }        int[][] sorted = balloons.clone();        Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1]));        int arrows = 1;        long arrowAt = sorted[0][1];        for (int i = 1; i < sorted.length; i++) {            if (sorted[i][0] > arrowAt) {            // this balloon starts after the arrow position                arrows++;                arrowAt = sorted[i][1];            }        }        return arrows;    }    public static void main(String[] args) {        System.out.println(minArrows(new int[][] {{10, 16}, {2, 8}, {1, 6}, {7, 12}}));        System.out.println(minArrows(new int[][] {{1, 2}, {3, 4}, {5, 6}, {7, 8}}));        System.out.println(minArrows(new int[][] {{1, 2}, {2, 3}, {3, 4}, {4, 5}}));        System.out.println(minArrows(new int[][] {{Integer.MIN_VALUE, Integer.MAX_VALUE}, {0, 1}}));        System.out.println(minArrows(new int[][] {}));    }}

24210

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Main {    static int[][] mergeBuggy(int[][] intervals) {        int[][] sorted = intervals.clone();        Arrays.sort(sorted, (a, b) -> a[0] - b[0]);        List<int[]> result = new ArrayList<>();        int[] current = sorted[0];        for (int i = 1; i < sorted.length; i++) {            if (sorted[i][0] <= current[1]) {                current[1] = sorted[i][1];            } else {                result.add(current);                current = sorted[i];            }        }        result.add(current);        return result.toArray(new int[0][]);    }    static int[][] mergeFixed(int[][] intervals) {        if (intervals.length == 0) {            return new int[0][];        }        int[][] sorted = intervals.clone();        Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));        List<int[]> result = new ArrayList<>();        int[] current = {sorted[0][0], sorted[0][1]};        for (int i = 1; i < sorted.length; i++) {            if (sorted[i][0] <= current[1]) {                current[1] = Math.max(current[1], sorted[i][1]);            } else {                result.add(current);                current = new int[] {sorted[i][0], sorted[i][1]};            }        }        result.add(current);        return result.toArray(new int[0][]);    }    static String show(int[][] intervals) {        StringBuilder sb = new StringBuilder();        for (int[] iv : intervals) {            sb.append('(').append(iv[0]).append(',').append(iv[1]).append(") ");        }        return sb.toString().trim();    }    public static void main(String[] args) {        System.out.println(show(mergeBuggy(new int[][] {{1, 10}, {2, 3}})) + " | " + show(mergeFixed(new int[][] {{1, 10}, {2, 3}})));        System.out.println(show(mergeBuggy(new int[][] {{1, 2}, {Integer.MIN_VALUE, 0}})) + " | " + show(mergeFixed(new int[][] {{1, 2}, {Integer.MIN_VALUE, 0}})));    }}

(1,3) | (1,10)(1,0) | (-2147483648,0) (1,2)

// File: Main.javapublic class Main {    static int canCompleteCircuit(int[] gas, int[] cost) {        long total = 0;        long tank = 0;        int start = 0;        for (int i = 0; i < gas.length; i++) {            long gain = (long) gas[i] - cost[i];            total += gain;            tank += gain;            if (tank < 0) {                 // failed to reach station i + 1 from the current start                start = i + 1;                tank = 0;            }        }        return total >= 0 ? start : -1;    }    public static void main(String[] args) {        System.out.println(canCompleteCircuit(new int[] {1, 2, 3, 4, 5}, new int[] {3, 4, 5, 1, 2}));        System.out.println(canCompleteCircuit(new int[] {2, 3, 4}, new int[] {3, 4, 3}));        System.out.println(canCompleteCircuit(new int[] {5}, new int[] {4}));        System.out.println(canCompleteCircuit(new int[] {}, new int[] {}));    }}

3-100

• Next: Bit Manipulation and Mathematical Patterns closes the algorithms module. The brute-force checker above already used a bit mask to enumerate subsets.
• When greedy fails: Dynamic Programming: Learn to Recognize Overlapping Subproblems handles the coin change case that defeated the greedy rule.
• Practice habit: never submit a greedy solution without trying to break it first. Write down the rule in one sentence, then spend two minutes looking for the input that makes the rule choose badly.