Greedy Interview Problems

Problem 1: Minimum Platforms

Statement: Given arrival and departure times of N trains, find the minimum number of platforms needed at a railway station so that no train waits.

Approach

This is a sweep line problem. Sort all events (arrivals and departures) chronologically. An arrival adds a train (+1 platform needed), a departure removes one (-1). The maximum concurrent trains at any point equals the minimum platforms needed.

Key Insight

We do not need to match specific trains to platforms. We only care about the maximum overlap — the peak number of trains present simultaneously.

Implementation

Complexity: Time O(n log n) for sorting, Space O(1).

Problem 3: Jump Game

Statement: Given an array where nums[i] represents the maximum jump length from position i, determine if you can reach the last index starting from index 0.

Approach (Greedy — Track Maximum Reach)

Maintain a variable max_reach = the farthest index reachable so far. Scan left to right: at each position i, if i > max_reach you are stuck. Otherwise, update max_reach = max(max_reach, i + nums[i]).

Implementation

Jump Game II (Minimum Jumps)

Find the minimum number of jumps to reach the end:

Greedy insight: At each "jump boundary," you commit to the jump that gives maximum forward reach. This BFS-like approach guarantees minimum jumps.

Complexity: Time O(n), Space O(1).

Problem 4: Candy Distribution

Statement: N children stand in a line with ratings. Each child must get at least 1 candy. Children with higher ratings than their neighbor must get more candies than that neighbor. Minimize total candies distributed.

Approach (Two-Pass Greedy)

One pass left-to-right handles the "better than left neighbor" constraint. A second pass right-to-left handles the "better than right neighbor" constraint. Take the maximum of both passes for each child.

Dry Run

Implementation

Why two passes work: The left pass ensures ascending sequences are handled. The right pass ensures descending sequences are handled. Taking the max satisfies both constraints simultaneously.

Complexity: Time O(n), Space O(n).

Summary Table

These four problems showcase different greedy flavors: sweep line, deficit tracking, forward reach, and bidirectional propagation. Each exploits the structure of the problem to avoid brute-force enumeration.