Greedy: Task Scheduling and Complex Interval Problems

Gas Station (LeetCode 134)

A circular route with $N$ gas stations. You start with gas[i] fuel and spend cost[i] to reach the next station. Find the starting index to complete the circuit.

Greedy Logic

Fundamental Observation: If starting at $A$ results in a negative tank at station $B$, then no station between $A$ and $B$ (inclusive) can be a successful starting point. Starting at any $C$ between $A$ and $B$ would only put you in a worse position at $B$ because you'd lose the positive cumulative fuel $A \to C$.

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalPerformance = 0; // Total gas - Total cost
    int currentTank = 0;      // Current fuel since starting from 'start'
    int start = 0;            // Candidate starting station

    for (int i = 0; i < gas.length; i++) {
        int gainRem = gas[i] - cost[i];
        totalPerformance += gainRem;
        currentTank += gainRem;
        
        if (currentTank < 0) {
            // Path from 'start' to 'i' fails; try starting at 'i + 1'
            start = i + 1;
            currentTank = 0;
        }
    }
    // If total fuel is sufficient, the found 'start' is guaranteed to work
    return totalPerformance >= 0 ? start : -1;
}

Complexity: Time $O(N)$, Space $O(1)$.

Partition Labels (LeetCode 763)

Partition a string into as many parts as possible so that each letter appears in at most one part.

Greedy Logic: Tracking Final Occurrences

1. Pre-record the index of the last occurrence of each character.
2. Iterate through the string. As you encounter characters, expand the current partition's end boundary to include the last occurrence of the character being visited.
3. When the current index equals the partition's end, you have reached the minimal boundary for a valid partition.

public List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) {
        last[s.charAt(i) - 'a'] = i;
    }

    List<Integer> result = new ArrayList<>();
    int start = 0, segmentEnd = 0;
    for (int i = 0; i < s.length(); i++) {
        segmentEnd = Math.max(segmentEnd, last[s.charAt(i) - 'a']);
        if (i == segmentEnd) {
            result.add(segmentEnd - start + 1);
            start = segmentEnd + 1;
        }
    }
    return result;
}

Boats to Save People (LeetCode 881)

Each boat can carry at most 2 people and a total weight of limit. Minimize the number of boats.

Greedy Logic: Greedy Pairing

Pair the heaviest person with the lightest person.

• If they fit together, great! Move both pointers center-ward.
• If they don't fit, the heaviest person must take a boat alone. Move only the "heavy" pointer.

public int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int lo = 0, hi = people.length - 1;
    int boats = 0;
    
    while (lo <= hi) {
        if (people[lo] + people[hi] <= limit) {
            lo++; // Lightest person fits
        }
        hi--; // Heaviest person takes a boat regardless
        boats++;
    }
    return boats;
}

Summary Summary Table