LeetCode Patterns Flashcards: Greedy Algorithms, Interval Scheduling, Jump Game

The greedy approach makes the locally optimal choice at each step, hoping to find the globally optimal solution. It works when a problem has the greedy choice property, meaning a locally optimal choice leads to a globally optimal solution, and optimal substructure. Unlike DP which considers all options, greedy commits to one choice and never reconsiders. Greedy is correct for interval scheduling, Huffman coding, Dijkstra's shortest path, and minimum spanning trees. It fails when local choices do not guarantee global optimality, like the zero-one knapsack.

Track the farthest position reachable from any position visited so far. Start at index zero with maximum reach equal to the value at index zero. Iterate through the array: at each position, update maximum reach as the greater of the current maximum reach and the current index plus the value at that index. If the current index exceeds maximum reach, you cannot proceed and the answer is false. If maximum reach reaches or exceeds the last index, the answer is true.

For the maximum non-overlapping intervals problem, sort intervals by end time and greedily select the earliest-ending interval that does not overlap with the last selected one. This works because finishing early leaves maximum room for future intervals. For the minimum meeting rooms problem, separate start and end times into two sorted arrays, then sweep through them chronologically: each start increments active meetings and each end decrements, tracking the maximum concurrent meetings as the answer. Both run in O of n log n due to sorting.

If the total gas across all stations is at least the total cost, a solution exists. To find the starting station, iterate through all stations tracking the current fuel balance. When the balance drops below zero, the start cannot be at or before the current station, so reset the balance and try the next station as the new candidate start. After one pass, the last candidate is the answer. This works because if a segment of the route causes a deficit, no station within that segment can be the start.

Sort intervals by their start times. Initialize the result with the first interval. For each subsequent interval, compare its start with the end of the last interval in the result. If the start is less than or equal to the end of the last interval, they overlap: merge them by updating the end to the maximum of both ends. If the start is greater, there is no overlap: add the new interval to the result as a separate entry. This runs in O of n log n for sorting plus O of n for the merge pass.

Sort intervals by end time. Iterate through and greedily keep intervals that do not overlap with the last kept interval. When two intervals overlap, remove the one ending later because it is more likely to overlap with future intervals. Count the number of removals needed. The minimum number of intervals to remove equals the total count minus the maximum number of non-overlapping intervals you can keep. This is equivalent to the interval scheduling maximization problem. ---