Study Notes by Niladri & AI

Session-12-Greedy

Properties1
tagsgreedy, interval-scheduling, interview-prep, java

17 min read

Practice Session 12: Greedy Algorithms

Overview

Greedy algorithms make the locally optimal choice at each step and never look back. The challenge at senior level is not coding the greedy — it is proving it is correct: an exchange argument (swap any non-greedy choice for the greedy one without making things worse) or a “greedy stays ahead” invariant (the greedy solution dominates all others at every step). Without being able to articulate the proof, you cannot distinguish a greedy that happens to pass test cases from one that is provably optimal — a critical gap in senior interviews. Interval scheduling is the canonical greedy domain; Gas Station and Jump Game are the archetypes of the “running sum / feasibility scan” subfamily.

Problem 1: Jump Game

Link: LeetCode 55

Quick Summary: Given nums[i] = maximum jump length from index i, determine if you can reach the last index from index 0.

Industry Context: Capacity feasibility checks in cloud autoscaling — “given this load profile across time windows, is there any sequence of scale-up steps that keeps the system within budget?” — are structural twins of Jump Game. The maxReach scan is also the basis of greedy link-state routing: each node advertises its farthest reachable neighbour, and the controller checks whether the accumulated reach spans the whole network.

Approach 1: DP

// O(n²) time  O(n) space
public static boolean canJumpDP(int[] nums) {
    int n = nums.length;
    boolean[] dp = new boolean[n];
    dp[0] = true;
    for (int i = 0; i < n; i++) {
        if (!dp[i]) continue;
        for (int j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) {
            dp[j] = true;
        }
    }
    return dp[n - 1];
}
  • Time: O(n²) — inner loop extends up to nums[i] steps for each reachable cell
  • Space: O(n) for the dp array
  • Tradeoff: Correct and intuitive; naturally models “which positions are reachable”. Fails at n = 10⁴ under tight time limits; motivates the greedy simplification.

Approach 2: Greedy maxReach Scan

// O(n) time  O(1) space
public static boolean canJumpGreedy(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;      // gap — unreachable
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}
  • Time: O(n)
  • Space: O(1)
  • Key Insight — Greedy Stays Ahead: Define maxReach(k) as the farthest index reachable after examining positions 0..k. Any strategy that picks a jump shorter than the maximum possible at position i yields a maxReach(k) ≤ the greedy’s maxReach(k) for all k (by induction: taking a shorter jump can only shrink the reachable frontier). Since “can we reach the end?” depends solely on whether maxReach ever reaches n-1, the greedy that always extends reach maximally dominates every other strategy. If any strategy succeeds, greedy succeeds too — and greedy is the simplest among all correct strategies.

Problem 2: Jump Game II

Link: LeetCode 45

Quick Summary: Same setup as LC 55; return the minimum number of jumps to reach the last index (a solution is always guaranteed).

Industry Context: Minimum-hop routing in SDN (Software Defined Networking) — a controller must route a packet from source to destination minimising the number of forwarding hops to reduce latency. The greedy “farthest-reach layer expansion” is structurally identical to BFS-based shortest-path in a hop-count metric, but O(n) rather than O(n²) because it collapses each BFS level into a single boundary variable.

Approach 1: BFS Levels

// O(n²) worst case  O(n) space
public static int jumpBFS(int[] nums) {
    int n = nums.length;
    if (n == 1) return 0;
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(0);
    visited[0] = true;
    int jumps = 0;
    while (!queue.isEmpty()) {
        jumps++;
        int size = queue.size();
        for (int k = 0; k < size; k++) {
            int i = queue.poll();
            for (int j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) {
                if (j == n - 1) return jumps;
                if (!visited[j]) { visited[j] = true; queue.offer(j); }
            }
        }
    }
    return jumps;
}
  • Time: O(n²) — in the worst case each level fans out to O(n) nodes
  • Space: O(n)
  • Tradeoff: Makes the BFS level-counting structure explicit, which is pedagogically useful. The O(n²) bound comes from the inner loop expanding up to n positions per BFS level.

Approach 2: Greedy Implicit Layers (Farthest Reach)

// O(n) time  O(1) space
public static int jumpGreedy(int[] nums) {
    int jumps = 0, curEnd = 0, curFarthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        curFarthest = Math.max(curFarthest, i + nums[i]);
        if (i == curEnd) {        // end of current BFS level — must jump
            jumps++;
            curEnd = curFarthest;
        }
    }
    return jumps;
}
  • Time: O(n)
  • Space: O(1)
  • Key Insight — Exchange Argument: Suppose an optimal solution OPT jumps from position p to some q where q < curFarthest (i.e., OPT does not jump as far as greedy could). Replace that jump with one to curFarthest. Because curFarthest >= q, the positions reachable in the next jump from curFarthest are a superset of those reachable from q — so no future jump in OPT becomes infeasible, and we may save a future jump. Therefore always extending to curFarthest is at least as good as any other choice, and the jump count is minimised.

Problem 3: Meeting Rooms II

Link: LeetCode 253

Quick Summary: Given intervals [start, end] representing meetings, return the minimum number of conference rooms required so all meetings can run simultaneously as scheduled.

Industry Context: This is Kubernetes pod scheduling at its core — given a set of jobs with start/end resource windows, what is the minimum number of worker nodes (rooms) needed? The same model governs AWS Lambda concurrency slot management, database connection pool sizing, and thread pool dimensioning for an HTTP server under a given request-duration distribution. The sweep-line variant is what query planners use to compute “maximum concurrent transactions” for lock-contention estimation.

Approach 1: Sort + Min-Heap Room Counter

// O(n log n) time  O(n) space
public static int minMeetingRoomsHeap(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);         // sort by start
    PriorityQueue<Integer> endTimes = new PriorityQueue<>(); // min-heap of end times
    for (int[] interval : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
            endTimes.poll();    // reuse the earliest-ending room
        }
        endTimes.offer(interval[1]);
    }
    return endTimes.size();
}
  • Time: O(n log n) — sort + n heap operations each O(log n)
  • Space: O(n) for the heap
  • Tradeoff: Intuitive: the heap models “rooms in use, sorted by when they become free”. Easy to extend to return which room is assigned to each meeting.

Approach 2: Sweep-Line / Event-Based

// O(n log n) time  O(n) space
public static int minMeetingRoomsSweep(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) {
        starts[i] = intervals[i][0];
        ends[i]   = intervals[i][1];
    }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int rooms = 0, maxRooms = 0, endPtr = 0;
    for (int s : starts) {
        if (s >= ends[endPtr]) { rooms--; endPtr++; }
        rooms++;
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}
  • Time: O(n log n)
  • Space: O(n) for the two sorted arrays
  • Key Insight — Exchange Argument: The minimum number of rooms equals the maximum number of meetings overlapping at any instant — a lower bound (you cannot do better) that greedy achieves exactly. When a new meeting starts at time s, if any existing meeting has already ended (ends[endPtr] <= s), we reuse that room. If we chose not to reuse it, we’d open a new room unnecessarily — a wasted resource that an exchange can always undo. The two-pointer walk over sorted starts and ends computes this in O(n) after the O(n log n) sort.

Problem 4: Gas Station

Link: LeetCode 134

Quick Summary: n gas stations in a circle; gas[i] fuel gained at station i, cost[i] fuel to travel to i+1. Find the unique starting station that allows completing the full circuit, or return -1 if impossible.

Industry Context: Circular load balancing in distributed systems — imagine shards in a consistent-hash ring where each shard has surplus or deficit capacity. The Gas Station algorithm finds the shard from which a re-balancing sweep can proceed without any shard ever going into capacity debt. It also models task token bucket routing: given a circular set of workers each producing/consuming tokens, find the worker from which a drain sweep stays non-negative throughout.

Approach 1: Brute Force (Try Each Start)

// O(n²) time  O(1) space
public static int canCompleteCircuitBrute(int[] gas, int[] cost) {
    int n = gas.length;
    for (int start = 0; start < n; start++) {
        int tank = 0;
        boolean ok = true;
        for (int step = 0; step < n; step++) {
            int i = (start + step) % n;
            tank += gas[i] - cost[i];
            if (tank < 0) { ok = false; break; }
        }
        if (ok) return start;
    }
    return -1;
}
  • Time: O(n²)
  • Space: O(1)
  • Tradeoff: Straightforward simulation. TLE at n = 10⁵. Useful to state first in an interview as the baseline that motivates the greedy skip insight.

Approach 2: Single-Pass Greedy (Total + Running Sum)

// O(n) time  O(1) space
public static int canCompleteCircuitGreedy(int[] gas, int[] cost) {
    int totalTank = 0, runningTank = 0, startCandidate = 0;
    for (int i = 0; i < gas.length; i++) {
        int net = gas[i] - cost[i];
        totalTank   += net;
        runningTank += net;
        if (runningTank < 0) {
            startCandidate = i + 1;
            runningTank = 0;
        }
    }
    return totalTank >= 0 ? startCandidate : -1;
}
  • Time: O(n)
  • Space: O(1)
  • Key Insight — Two-Part Greedy Correctness:
    1. Existence (total check): If sum(gas) >= sum(cost), a solution is guaranteed. The total surplus means the “debt” accumulated in hard sections must be repaid by later surplus sections in some rotation — a solution must exist.
    2. Candidate skip (greedy stays ahead): If starting at s we exhaust the tank at station f, then no station m in (s, f) can be a valid start. Proof by contradiction: starting at m (tank = 0) and reaching f would require a non-negative running sum from m to f-1. But the running sum from s to m-1 was non-negative (we were still going), so the prefix from m to f-1 must be negative (otherwise we wouldn’t have failed at f starting from s). Starting fresh at m with zero tank over that same negative-sum stretch fails — so m is eliminated. We safely advance startCandidate past f in one step.

Problem 5: Non-overlapping Intervals

Link: LeetCode 435

Quick Summary: Given an array of intervals, return the minimum number of intervals to remove so that the remaining intervals are non-overlapping. (Equivalent: maximise the number of non-overlapping intervals kept.)

Industry Context: Calendar defragmentation — given a user’s calendar with overlapping events, find the smallest set of events to remove to free a contiguous block. In OS scheduling, this is CPU burst scheduling / Activity Selection: given a set of processes with execution windows, select the maximum number that can run without preemption, equivalent to minimising removals. The same algorithm drives advertisement slot scheduling (maximising non-overlapping ad impressions in a broadcast slot).

Approach 1: Sort by Start + DP (Activity Selection DP)

// O(n²) time  O(n) space
public static int eraseOverlapIntervalsDP(int[][] intervals) {
    if (intervals.length == 0) return 0;
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    int n = intervals.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int maxKeep = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (intervals[j][1] <= intervals[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxKeep = Math.max(maxKeep, dp[i]);
    }
    return n - maxKeep;
}
  • Time: O(n²)
  • Space: O(n)
  • Tradeoff: The DP makes the subproblem structure explicit: dp[i] = size of the largest compatible set ending at interval i. Correct; the O(n log n) greedy collapses this to a single-variable scan because sorting by end time makes the greedy choice obvious.

Approach 2: Sort by End Time + Greedy (Earliest Deadline First)

// O(n log n) time  O(1) space after sort
public static int eraseOverlapIntervalsGreedy(int[][] intervals) {
    if (intervals.length == 0) return 0;
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);  // sort by END time
    int removals = 0, prevEnd = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] >= prevEnd) {
            prevEnd = interval[1];  // keep — no overlap
        } else {
            removals++;             // remove — overlaps with last kept
        }
    }
    return removals;
}
  • Time: O(n log n) — sort dominates; one-pass scan is O(n)
  • Space: O(1) after sort (or O(n) counting sort space)
  • Key Insight — Exchange Argument (Activity Selection canonical proof):
    At any conflict point where two intervals overlap, the greedy keeps whichever ends earlier (already sorted). Suppose OPT keeps interval A but greedy keeps B where end(B) <= end(A). Replace A with B in OPT: since end(B) <= end(A), interval B ends no later than A, so B is compatible with every interval OPT keeps after A. The replacement does not reduce the number of intervals kept. By induction over all conflicts, greedy makes exchanges that are always at least as good — so greedy achieves the maximum compatible set size, hence the minimum removals.

How to Prove a Greedy is Correct

This is the section that separates senior-level answers from junior ones. There are two main techniques.

1. Exchange Argument

Template: Assume an optimal solution OPT makes a different choice from greedy at some step. Show that you can exchange OPT’s choice for the greedy choice without making the solution worse (same or lower cost, same or higher count). By repeatedly applying exchanges you transform OPT into the greedy solution without increasing cost — so greedy is optimal.

When to use: Interval scheduling (Meeting Rooms, Non-overlapping Intervals), Jump Game II, any problem where you sort by a key and make one-pass decisions.

Example sketch (Non-overlapping Intervals):

“OPT keeps interval A (ends at time 10). Greedy keeps interval B (ends at time 7, same start). Replace A with B in OPT: B ends earlier, so every interval after A that was compatible is still compatible after B. Removal count unchanged or improved. QED.”

2. Greedy Stays Ahead

Template: Define a progress metric (e.g., maxReach, startCandidate). Show by induction that after each step the greedy’s metric value is at least as good as any other algorithm’s metric value. If the greedy reaches the goal whenever any algorithm does, greedy is optimal.

When to use: Jump Game (maxReach), Gas Station (running tank), covering problems, any “can we reach X?” feasibility scan.

Example sketch (Jump Game):

“Define G(k) = greedy’s maxReach after k steps. Claim: G(k) >= A(k) for any strategy A. Base case trivial. Inductive step: at position i, greedy sets G(k+1) = max(G(k), i + nums[i]). Strategy A sets A(k+1) <= i + nums[i] (can’t exceed max jump). Since G(k) >= A(k), G(k+1) >= A(k+1). If G(k) >= n-1, greedy succeeds — so if A succeeds, greedy also succeeds.”

3. How to Spot When Greedy FAILS

Greedy fails when a locally optimal choice forecloses a globally better path — i.e., when decisions interact across time.

ProblemWhy Greedy Fails
Coin Change (arbitrary denominations, e.g., {1,3,4}, target 6)Greedy picks 4+1+1 (3 coins); DP finds 3+3 (2 coins). The greedy coin blocks the better two-coin path.
0/1 KnapsackTaking the highest value-density item may use capacity that a combination of smaller items would fill more profitably. Greedy can’t un-take an item.
Shortest Path (negative weights)Dijkstra (greedy min-dist selection) is incorrect with negative edges — a later, seemingly longer path may become shorter via a negative edge.
Matrix Chain MultiplicationLocally cheapest bracket may produce globally expensive nested multiplications. Requires DP over all sub-ranges.

The tell: if the problem has “overlapping subproblems” (the same subproblem recurs) or “choice affects future feasibility in a complex way”, reach for DP or backtracking first, then check if the DP recurrence degenerates to a single greedy choice.

Greedy vs DP Decision Table

SignalLean TowardReason
”Minimum removals / maximum kept from a sorted set”GreedyExchange argument almost always applies after sorting by end time
”Minimum cost path through a grid / DAG”DPEach cell’s optimal cost depends on choices from multiple prior cells
”Feasibility: can we reach / complete?” with monotone metricGreedymaxReach, runningTank are monotone invariants; no backtracking needed
”Count/enumerate all combinations/subsets”Backtracking / DPNo single greedy choice captures all valid states
”Coin change / unbounded knapsack”DPDenominations interact; greedy coin choice can block better solutions
”Interval scheduling: max non-overlapping”GreedyClassic activity selection — exchange argument proven in 1971 (Karp)
“Interval scheduling: minimum covers / partitions”GreedySweep-line / min-heap approach; minimum rooms = maximum overlap
”Edit distance / LCS / string alignment”DPEach position depends on a 2-D table of prior alignments
”DP recurrence has only one branch (no max/min over two options)“GreedyIf dp[i] = dp[i-1] + f(i) with no choice, it’s a greedy disguised as DP
”Problem has optimal substructure BUT also overlapping subproblems”DPBoth conditions together → memoisation; greedy would be incorrect

Key Takeaways

Pattern Recognition Triggers

  • “Can you reach the end / complete the task?” with a per-step capacity → maxReach greedy scan (Jump Game)
  • “Minimum jumps / minimum hops” → greedy implicit BFS layers (Jump Game II), not full BFS
  • “Minimum rooms / workers / machines for overlapping intervals” → sort by start + min-heap end times OR sweep-line (Meeting Rooms II)
  • “Circular feasibility: can a sweep complete without going negative?” → total sum check + running sum with candidate reset (Gas Station)
  • “Minimum removals from intervals” → sort by END time + greedy keep (Non-overlapping Intervals / Activity Selection)
  • Locally optimal → globally optimal is the greedy guarantee; always articulate the exchange argument or greedy-stays-ahead proof

Common Gotchas

  • Wrong sort key: Non-overlapping Intervals requires sorting by end time, not start. Sorting by start gives wrong answers for intervals like [1,10] vs [2,3],[4,5].
  • Tie-breaking in sort: Meeting Rooms II sweep-line requires processing end events before start events at the same time (t). A meeting ending at t should free a room before a meeting starting at t occupies one. Off-by-one here causes over-counting by 1.
  • Gas Station total check omission: Returning startCandidate without checking totalTank >= 0 will return a wrong answer for infeasible inputs where no circuit is possible.
  • Confusing Jump Game I and II: LC 55 asks can you reach (boolean, greedy returns immediately); LC 45 asks minimum jumps (count, greedy counts layer crossings). Different termination conditions.
  • Proving correctness under pressure: always have one sentence ready: “This is an exchange argument — if OPT makes a different choice, I can swap it for the greedy choice without increasing cost.”

System Design Connections

Greedy AlgorithmSystem Design Analogue
Meeting Rooms II min-heapKubernetes scheduler — minimum node count for a pod workload with resource windows; AWS Lambda concurrency slot allocation
Sweep-line max-overlapDatabase query planner — “maximum concurrent transactions” for lock contention modelling; connection pool sizing
Gas Station circular scanConsistent-hash ring rebalancing — finding the shard from which a capacity-drain sweep stays non-negative; circular token-bucket routing
Non-overlapping Intervals (Activity Selection)CPU burst scheduling (EDF/FIFO); advertisement slot scheduling (maximise non-overlapping impressions); calendar defrag tools
Jump Game maxReachCloud autoscaling feasibility check — can scale-up steps keep the system within budget across forecast windows?; SDN hop-count route feasibility
Jump Game II greedy layersMinimum-hop packet routing in SDN; Dijkstra on unit-weight graphs — the O(n) greedy replaces the O(n²) BFS when positions form a sorted sequence

Graph View

Backlinks