Navigation

DSA greedy 12 min read

Greedy Algorithm Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the greedy exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and a common pitfall. Try the problems first — and for each, make sure you can say why the greedy choice is provably safe, not just that it works.

Q1. Assign Cookies

Idea: Sort both children (greed) and cookies (size) ascending. Walk both with two pointers, giving the smallest cookie that satisfies the current child to the least-greedy unserved child. Spending the smallest sufficient cookie never wastes a bigger one.

Complexity: O(n log n) time (the sorts), O(1) extra space.

#include <vector>
#include <algorithm>

int findContentChildren(std::vector<int> g, std::vector<int> s) {
    std::sort(g.begin(), g.end());
    std::sort(s.begin(), s.end());
    int child = 0, cookie = 0;
    while (child < (int)g.size() && cookie < (int)s.size()) {
        if (s[cookie] >= g[child]) child++; // this cookie satisfies the child
        cookie++;                           // either way, this cookie is used up
    }
    return child;
}

import java.util.Arrays;

int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int child = 0, cookie = 0;
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) child++; // this cookie satisfies the child
        cookie++;                           // either way, cookie is used up
    }
    return child;
}

function findContentChildren(g, s) {
  g.sort((a, b) => a - b);
  s.sort((a, b) => a - b);
  let child = 0, cookie = 0;
  while (child < g.length && cookie < s.length) {
    if (s[cookie] >= g[child]) child++; // this cookie satisfies the child
    cookie++;                           // either way, cookie is used up
  }
  return child;
}

def find_content_children(g, s):
    g.sort()
    s.sort()
    child = cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:  # this cookie satisfies the child
            child += 1
        cookie += 1                # either way, cookie is used up
    return child

Pitfall: Don’t always advance the child pointer. Advance it only when a cookie satisfies it; the cookie pointer advances every iteration because an undersized cookie can’t satisfy anyone larger either.

Q2. Fractional Knapsack

Idea: Sort items by value-to-weight ratio descending. Greedily take whole items while they fit; for the first item that doesn’t fit, take the fraction that fills the remaining capacity. Because fractions are allowed, the densest value always belongs in the bag — this is the greedy-choice property that fails for 0/1 knapsack.

Complexity: O(n log n) time, O(1) extra space (besides the sort).

#include <vector>
#include <algorithm>

// items: {value, weight}. Returns max value for capacity W.
double fractionalKnapsack(std::vector<std::pair<double,double>> items, double W) {
    std::sort(items.begin(), items.end(), [](auto& a, auto& b){
        return a.first / a.second > b.first / b.second; // ratio descending
    });
    double total = 0;
    for (auto& [value, weight] : items) {
        if (W <= 0) break;
        double take = std::min(weight, W);
        total += value * (take / weight); // full item or a fraction
        W -= take;
    }
    return total;
}

import java.util.Arrays;

// items[i] = {value, weight}. Returns max value for capacity W.
double fractionalKnapsack(double[][] items, double W) {
    Arrays.sort(items, (a, b) ->
        Double.compare(b[0] / b[1], a[0] / a[1])); // ratio descending
    double total = 0;
    for (double[] it : items) {
        if (W <= 0) break;
        double take = Math.min(it[1], W);
        total += it[0] * (take / it[1]); // full item or a fraction
        W -= take;
    }
    return total;
}

// items: [[value, weight], ...]. Returns max value for capacity W.
function fractionalKnapsack(items, W) {
  items.sort((a, b) => b[0] / b[1] - a[0] / a[1]); // ratio descending
  let total = 0;
  for (const [value, weight] of items) {
    if (W <= 0) break;
    const take = Math.min(weight, W);
    total += value * (take / weight); // full item or a fraction
    W -= take;
  }
  return total;
}

# items: list of (value, weight). Returns max value for capacity W.
def fractional_knapsack(items, W):
    items.sort(key=lambda it: it[0] / it[1], reverse=True)  # ratio descending
    total = 0.0
    for value, weight in items:
        if W <= 0:
            break
        take = min(weight, W)
        total += value * (take / weight)  # full item or a fraction
        W -= take
    return total

Pitfall: This greedy is correct only because fractions are allowed. For 0/1 knapsack (all-or-nothing items) the ratio rule fails — use dynamic programming.

Q3. Jump Game

Idea: Track the farthest index reachable so far. Sweep left to right; if you ever stand on an index beyond that reach, you’re stuck. Otherwise extend the reach by i + nums[i]. You can reach the end iff the reach ever covers the last index.

Complexity: O(n) time, O(1) space.

#include <vector>
bool canJump(const std::vector<int>& nums) {
    int reach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > reach) return false;          // this index is unreachable
        reach = std::max(reach, i + nums[i]); // extend the frontier
    }
    return true;
}

boolean canJump(int[] nums) {
    int reach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > reach) return false;          // this index is unreachable
        reach = Math.max(reach, i + nums[i]); // extend the frontier
    }
    return true;
}

function canJump(nums) {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;            // this index is unreachable
    reach = Math.max(reach, i + nums[i]);   // extend the frontier
  }
  return true;
}

def can_jump(nums):
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:                  # this index is unreachable
            return False
        reach = max(reach, i + jump)   # extend the frontier
    return True

Pitfall: Once i > reach you must stop — continuing reads indices you can never actually stand on and can produce a false positive.

Q4. Gas Station

Idea: If the total gas is less than total cost, no start works — return -1. Otherwise a valid start exists and is unique-ish: track a running tank from the current candidate start; the moment it goes negative at station i, no start in [start..i] can work, so the next candidate is i + 1.

Complexity: O(n) time, O(1) space.

#include <vector>
int canCompleteCircuit(const std::vector<int>& gas, const std::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;
}

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;
}

function canCompleteCircuit(gas, cost) {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const 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;
}

def can_complete_circuit(gas, cost):
    total = tank = start = 0
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff
        tank += diff
        if tank < 0:            # restart after i
            start = i + 1
            tank = 0
    return start if total >= 0 else -1

Pitfall: The local tank resets to 0 at each restart, but total must accumulate across the whole array — it’s the global feasibility check. Mixing up the two breaks the answer.

Q5. Merge Intervals

Idea: Sort intervals by start. Walk through; if the current interval starts at or before the end of the last merged one, extend that end; otherwise start a new interval. Sorting guarantees any overlap is with the most recent block.

Complexity: O(n log n) time, O(n) space for the output.

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> merge(std::vector<std::vector<int>> intervals) {
    std::sort(intervals.begin(), intervals.end());
    std::vector<std::vector<int>> out;
    for (auto& iv : intervals) {
        if (!out.empty() && iv[0] <= out.back()[1])
            out.back()[1] = std::max(out.back()[1], iv[1]); // overlap: extend
        else
            out.push_back(iv);                              // disjoint: new block
    }
    return out;
}

import java.util.*;

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() && iv[0] <= out.get(out.size() - 1)[1])
            out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], iv[1]);
        else
            out.add(iv);
    }
    return out.toArray(new int[0][]);
}

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const iv of intervals) {
    const last = out[out.length - 1];
    if (last && iv[0] <= last[1]) last[1] = Math.max(last[1], iv[1]); // extend
    else out.push(iv.slice());                                       // new block
  }
  return out;
}

def merge(intervals):
    intervals.sort()
    out = []
    for iv in intervals:
        if out and iv[0] <= out[-1][1]:
            out[-1][1] = max(out[-1][1], iv[1])  # overlap: extend
        else:
            out.append(list(iv))                 # disjoint: new block
    return out

Pitfall: When extending, take max(last_end, current_end) — a later interval may be fully contained in the previous one, so blindly assigning its end can shrink the merged block.

Q6. Non-overlapping Intervals

Idea: This is activity selection flipped: the maximum number of non-overlapping intervals you can keep is found by sorting on end time and greedily keeping each interval whose start is at or after the last kept end. The minimum to remove is n − kept.

Complexity: O(n log n) time, O(1) extra space.

#include <vector>
#include <algorithm>

int eraseOverlapIntervals(std::vector<std::vector<int>> intervals) {
    std::sort(intervals.begin(), intervals.end(),
              [](auto& a, auto& b){ return a[1] < b[1]; }); // by end
    int kept = 0, lastEnd = INT_MIN;
    for (auto& iv : intervals)
        if (iv[0] >= lastEnd) { kept++; lastEnd = iv[1]; }
    return (int)intervals.size() - kept;
}

import java.util.Arrays;

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

function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]); // by end
  let kept = 0, lastEnd = -Infinity;
  for (const [start, end] of intervals)
    if (start >= lastEnd) { kept++; lastEnd = end; }
  return intervals.length - kept;
}

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda iv: iv[1])  # by end
    kept, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            kept += 1
            last_end = end
    return len(intervals) - kept

Pitfall: Sort by end, not start. Sorting by start and greedily keeping leads you to keep a long early interval that blocks many shorter ones — the classic wrong greedy for interval scheduling.

Q7. Minimum Number of Platforms

Idea: A platform is needed for every train present at the same time, so the answer is the maximum number of overlapping intervals. Sort arrivals and departures separately, then sweep with two pointers: each arrival before the next departure needs a new platform; each departure frees one. Track the running and maximum count.

Complexity: O(n log n) time, O(1) extra space (besides the sorts).

#include <vector>
#include <algorithm>

int minPlatforms(std::vector<int> arr, std::vector<int> dep) {
    std::sort(arr.begin(), arr.end());
    std::sort(dep.begin(), dep.end());
    int i = 0, j = 0, cur = 0, best = 0, n = arr.size();
    while (i < n) {
        if (arr[i] <= dep[j]) { cur++; i++; best = std::max(best, cur); }
        else { cur--; j++; } // a train has departed, free a platform
    }
    return best;
}

import java.util.Arrays;

int minPlatforms(int[] arr, int[] dep) {
    Arrays.sort(arr);
    Arrays.sort(dep);
    int i = 0, j = 0, cur = 0, best = 0, n = arr.length;
    while (i < n) {
        if (arr[i] <= dep[j]) { cur++; i++; best = Math.max(best, cur); }
        else { cur--; j++; } // a train has departed, free a platform
    }
    return best;
}

function minPlatforms(arr, dep) {
  arr.sort((a, b) => a - b);
  dep.sort((a, b) => a - b);
  let i = 0, j = 0, cur = 0, best = 0;
  while (i < arr.length) {
    if (arr[i] <= dep[j]) { cur++; i++; best = Math.max(best, cur); }
    else { cur--; j++; } // a train has departed, free a platform
  }
  return best;
}

def min_platforms(arr, dep):
    arr.sort()
    dep.sort()
    i = j = cur = best = 0
    n = len(arr)
    while i < n:
        if arr[i] <= dep[j]:   # a train arrives before the next departs
            cur += 1
            i += 1
            best = max(best, cur)
        else:                  # a train has departed, free a platform
            cur -= 1
            j += 1
    return best

Pitfall: Use arr[i] <= dep[j] (not <) if a train arriving exactly when another departs still needs its own platform — match the comparison to the problem’s tie rule. Also loop only until arrivals are exhausted; remaining departures can’t raise the peak.

That’s the full answer sheet. Back to the greedy exercises, or continue to dynamic programming for the problems where greedy isn’t enough.