Greedy Algorithms

Intuition 1: Track maximum reachable index

We don't need to simulate every path. Track the furthest index we can reach at any point. For each index i, if i > maxReach, we're stuck — return false. Otherwise update maxReach = max(maxReach, i + nums[i]). If we reach the last index, return true.

Intuition 1: Level-by-level BFS thinking

Think of it as BFS levels: from current "level" of reachable positions, find the furthest we can reach in one more jump — that's the next level. When we step out of the current level boundary, we must have jumped, so increment count.

Intuition 1: Sort by start, merge overlapping neighbors

Sort intervals by start time. Then scan: if current interval overlaps with last merged (current.start ≤ last.end), merge by extending end. Otherwise add current as new interval. Two intervals overlap when start of later ≤ end of earlier.

Intuition 1: Maximize kept intervals = minimize removed

Sort by END time. Greedily keep intervals with earliest end time (they leave most room for future intervals). When two intervals overlap, remove the one with the later end (greedy: keep earlier-ending). Count how many we remove.

Intuition 1: O(n²) brute force — try each starting station

For each station as start, simulate the full circuit. Track cumulative gas. If tank goes negative, this start fails. O(n²).

Intuition 1: O(n) greedy — track farthest reachable index

Track the maximum index reachable so far. At each position i, if i > maxReach, we can never reach here — return false. Otherwise extend maxReach.

Intuition 1: Two-pass greedy — left→right then right→left

Pass 1 (left→right): give each child 1 candy. If ratings[i] > ratings[i-1], child i gets one more than child i-1. Pass 2 (right→left): if ratings[i] > ratings[i+1], child i must have more than child i+1 — take the max of current and right+1. Sum everything.

Intuition 1: O(n) greedy — BFS levels

Think of it as BFS where each "level" = one jump. Track the farthest reachable position from the current level. When you exhaust the current level's range, you must jump — that counts as one jump. The farthest reachable from the current level becomes the new level boundary.

Intuition 1: Precompute last occurrence, then greedy merge

For each character, find its last occurrence in the string. Then scan left→right, tracking the farthest last occurrence seen so far. When current index reaches that farthest position, we've found a partition — all characters from start to here only appear within this segment.

Intuition 1: Math formula — most frequent task drives the answer

The most frequent task determines the minimum time. If task A appears f times, we need at least (f-1)*(n+1)+1 slots. But if there are multiple tasks with frequency f, each one fills a "slot" in the last chunk: result = max(tasks.length, (maxFreq-1)*(n+1) + countOfMaxFreq).

Intuition 1: Sort both, greedily assign smallest sufficient cookie

Sort children by greed factor, sort cookies by size. Use two pointers: try to satisfy the least greedy child with the smallest cookie. If cookie ≥ greed, assign it and move both pointers. If not, try a bigger cookie.

Intuition 1: Sort by end, shoot as far right as possible

Sort balloons by end position. Greedily shoot at the end of the first balloon. This arrow also bursts any overlapping balloon whose start ≤ arrow position. Move to the next unbursted balloon and repeat.