0. Intervals & Greedy Foundation • Invariant Proof & Speed-Run

Canonical LeetCode:Jump Game (LC 55)Jump Game II (LC 45)Gas Station (LC 134)Partition Labels (LC 763)Video Stitching (LC 1024)IPO (LC 502)Integer to Roman (LC 12)Hand of Straights (LC 846)Merge Triplets to Form Target Triplet (LC 1899)Maximum Number of Weeks for Which You Can Work (LC 1953)Valid Parenthesis String (LC 678)

2Greedy

choices in order ➔ locally best option (exchange argument) ➔ never undone

Greedy (Exchange Argument, Furthest Reach)

Spot it when: Each step offers a choice (how far to jump, where to start, where to cut), and you can argue that the locally best option never has to be undone: it keeps every option any other choice would keep.

Mode 2 · Greedy

Python

1	def can_jump(nums: list[int]) -> bool:
2	"""Jump Game: greedy furthest reach.
3	Time: O(N) \| Space: O(1)
4	"""
5	reach = 0 # Furthest index some run of jumps can land on so far
6
7	for i in range(len(nums)):
8	# 1. Stop When Index i Is Unreachable, Otherwise Extend reach:
9	# An index past reach has no jump landing on it, so it must never extend reach with its own jump;
10	# check that first. Otherwise take the larger of reach and i + nums[i], since a longer reach always
11	# contains every index a shorter one does.
12	if i > reach:
13	return False
14	reach = max(reach, i + nums[i])
15
16	return True # The loop stood on every index, the last one included

You never need the path, only how far any path can get: keep reach, the furthest index a run of jumps can land on so far, and at every index you can stand on extend it with reach = max(reach, i + nums[i]). A jump may be shorter than nums[i], so every index up to reach can be landed on and the reachable indices always form one block 0..reach; taking the larger reach can never cost an option, because a longer block contains every index of a shorter one. That is the greedy argument in general: the locally best choice keeps everything any other choice would keep, so it never has to be undone. The trap is the order of the two lines: check if i > reach: return False before reading nums[i], because an index past reach can't be stood on, and letting its jump extend reach makes [3,2,1,0,4] return True.

Gotchas1 of 3

The trap
Gotcha 1: Updating reach before checking i > reach
Mistake
```
reach = max(reach, i + nums[i])
if i > reach:
    return False
```
Fix
```
if i > reach:
    return False
reach = max(reach, i + nums[i])
```
What happens: An index past reach cannot be stood on. So its jump must never count. Updating first lets that index extend reach with its own jump. Then i > reach is False, and the loop goes on as if index i could be reached.
Example: nums = [3, 2, 1, 0, 4]
Mistake: returns TrueFix: returns False
Gotcha 2: Looping to len(nums) - 1 and skipping the last index
Mistake
```
for i in range(len(nums) - 1):
```
Fix
```
for i in range(len(nums)):
```
What happens: The check i > reach runs only for the indices the loop visits. range(len(nums) - 1) stops before the last index. So the last index is never checked, and the function returns True even when it cannot be reached.
Example: nums = [3, 2, 1, 0, 4]
Mistake: returns TrueFix: returns False
Gotcha 3: Writing reach = i + nums[i] without max
Mistake
```
reach = i + nums[i]
```
Fix
```
reach = max(reach, i + nums[i])
```
What happens: A short jump can come after a long one. Then i + nums[i] is smaller than the current reach. The plain assignment lowers reach, and the loop stops at an index that could be reached.
Example: nums = [4, 1, 0, 0, 0]
Mistake: returns FalseFix: returns True

Built on the mental models above

Interval SchedulingInterval Scheduling (Activity Selection, Greedy by End Time)
Sort by end instead of start, and count or drop intervals instead of merging them.
End-Time GroupsInterval Grouping (Minimum Arrows to Burst Balloons)
Count the groups of intervals that share a point instead of the intervals to remove: shoot at the end of the first interval not yet hit.
Sweep LineSweep Line (Line Sweep)
Break each interval into a start event and an end event, sort the events, and track how many are open.

The Intervals & Greedy Decision Rule

When facing an unseen interval or greedy problem, ask in this order:

Step 1.Does the problem ask to merge overlapping ranges or insert a new range?

Compare curr.start <= prev.end and extend prev.end = max(prev.end, curr.end).

Step 2.Does the problem ask for the minimum intervals to remove or maximum non-overlapping set?

Non-overlapping Intervals (LC 435)Maximum Length of Pair Chain (LC 646)

Sort by end time and greedily retain the earliest ending interval that starts at or after the last kept end.

Step 3.Does the problem track simultaneous active overlaps (rooms, passengers)?

Create +1 (start) and -1 (end) events, sorting end events first at equal timestamps.

Step 4.Does each step offer a choice where the locally best option never has to be undone (jumps, gas stations, partitions)?

➔ Greedy

Prove with an exchange argument that the greedy pick keeps every option another pick would, then take it at every step.

Step 5.Must you pick the fewest points that touch every interval, or split the intervals into the fewest groups that each share a point?

Minimum Number of Arrows to Burst Balloons (LC 452)Maximum Length of Pair Chain (LC 646)

Sort by end and shoot at the end of the first interval not yet hit; an interval that starts at or before that spot is already hit.

Pattern Architecture & Invariant Design Masterclass

One idea runs through every card here: sort first, then keep one running value, and an O(n²) comparison problem becomes O(n).

Interval sweeps. An interval is a start and an end — a meeting from 9 to 10, a booking from the 3rd to the 6th. Asked "which of these overlap?", the instinct is to compare every pair: O(n²). But sort by start time and the problem changes shape: an interval that overlaps anything already merged must overlap the block being built, merged[-1], so a single left-to-right pass comparing each interval only to the one it is currently accumulating is enough. The sort costs O(n log n), the sweep O(n), and the sort dominates.

Greedy choices. A greedy problem offers a choice at each step. The greedy rule picks the locally best option and never goes back. It is correct only when you can argue that no other option could have done better. Jump Game keeps one number, reach, in place of every possible path.

The invariants to say out loud:

Greedy: "Everything before index i is decided, and one number summarizes what it allows."

How this plays out in actual problems:

🟢 Scenario A: Interval Merging & Absorption (Sort by Start Time)

In interval merging (like Merge Intervals LC 56), we consolidate overlapping blocks into unified continuous spans.
The Rule: Sort intervals by start time. Iterate left-to-right. If incoming[0] <= merged[-1][1], expand the current interval using merged[-1][1] = max(merged[-1][1], incoming[1]). Otherwise, append incoming as a new disjoint block.
The Code: if incoming[0] <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], incoming[1])

🔵 Scenario B: Earliest Finish Time Greedy Scheduling (Sort by End Time)

In non-overlapping interval scheduling (like LC 435 / LC 452), we want to maximize the count of mutually compatible intervals.
The Rule: Sort intervals by end time. Greedily select the interval that finishes earliest. Any subsequent interval whose start < current_end must be removed/skipped.
The Code: if start >= prev_end: prev_end = end; count += 1

💡 The Ultimate Takeaway Decision Rule:
When analyzing an interval or sequence query problem, ask: "Are we merging overlapping spans, scheduling non-overlapping intervals, counting overlaps, or making a one-way choice?"

Consolidating Overlapping Ranges ➔ Sort by start time x[0], sequential absorption ( $O(N \log N)$ ).

Maximizing Non-Overlapping / Min Removals ➔ Sort by end time x[1], greedy earliest finish selection ( $O(N \log N)$ ).

Concurrent Resource Peak (Meeting Rooms II) ➔ Chronological sweep-line boundary events (t, +1) & (t, -1) ( $O(N \log N)$ ).

One-way choice with a proof ➔ Greedy with a single running value, such as reach ( $O(N)$ ).

📦 1. Interval Merge & Absorption (LC 56 & 57)

Mental Model: Sort intervals by start time. After sorting, an interval that overlaps anything already merged must overlap the block being built, merged[-1], so earlier blocks are never checked again.
Code: see the Merge Intervals card.

⏱️ 2. Earliest Finish Time Greedy Scheduling (LC 435 & 452)

Mental Model: To leave maximal room for subsequent intervals, always pick the interval that finishes earliest. Sorting by end time guarantees optimal greedy choice.
LC 435 vs. LC 452: In Non-overlapping Intervals (LC 435), intervals that only touch do not overlap, so the blueprint keeps an interval when start >= prev_end. In Minimum Number of Arrows to Burst Balloons (LC 452), balloons that touch are burst by the same arrow, so a new arrow is needed only when start > prev_end.
Code: see the Interval Scheduling card.

📈 3. Sweep-Line Concurrency & Meeting Rooms II (LC 253)

Mental Model: Decompose intervals into discrete point events: +1 room at start time, -1 room at end time. Sort events chronologically.
Code: see the Sweep Line card.

Understanding Invariants: Interval Sweeps & Greedy Running Values

After sorting by start, anything that overlaps the interval I am building is the very next one I will see.

Interval sweeps sort chronologically to turn quadratic pairwise checks into single O(N) passes, and greedy passes keep one running value that summarizes everything already decided.

Interval Overlap Absorption Invariant

Condition: If incoming[0] <= merged[-1][1]

Action: merged[-1][1] = max(merged[-1][1], incoming[1])

Because intervals are sorted by start, overlapping intervals must be adjacent and can be absorbed into the running block.

Earliest Finish Time Invariant

Condition: If start >= prev_end

Action: prev_end = end; count += 1

Keeping the interval that ends earliest leaves the most room for every interval that comes after it.

Common Questions

"Do [1, 3] and [3, 5] overlap? Which character in my code decides that?"

It depends on the problem, and you must ask before you write code. If intervals that share an endpoint count as overlapping (Merge Intervals), the test is incoming[0] <= merged[-1][1]. The <= merges them. If touching intervals do not count as overlapping (Non-overlapping Intervals), the test is start >= prev_end to keep one. The only difference is one character, < or <=, and it changes the answer.

Coach discussion points

1.
"Do [1,3] and [3,5] overlap? Which character in your code decides that, and what happens if I want the other behaviour?" — Tests whether the convention was a deliberate decision or an accident. Candidates who ask this before coding score highest.
2.
"Your merge loop has an emit inside it. Run me through [[1,4]] — a single interval — line by line." — Discovers the missing final flush by tracing rather than by being told. The cheapest possible test, and the one most solutions fail.
3.
"Same list of meetings, but now I ask how many rooms I need instead of which blocks are busy. What changes about your approach, and why isn't merging enough?" — Separates "the intervals touch" from "how many are simultaneously live", which is the single most common conflation in this pattern.

Complexity analysis

Merge Intervals — Time O(n log n), Space O(n). The sort dominates completely; the sweep after it is a single O(n) pass with O(1) work per interval. If the input arrives already sorted, the whole thing is O(n) — say that, because it is the follow-up question. Space is O(n) for the output, plus O(log n) for the sort's own stack; if you may modify the input in place, the auxiliary space is O(log n).

Meeting Rooms II — Time O(n log n), Space O(n). Sort O(n log n), plus n heap pushes and up to n pops at O(log n) each — also O(n log n). Neither dominates asymptotically. The heap holds at most n end times.

Production Systems Deployment & Motivation

A calendar service holds a room's bookings and must display them as consolidated blocks — three back-to-back meetings from 9–10, 9:30–11, and 10:45–12 should render as one busy block 9–12, not three overlapping bars. It must also answer the harder operational question: how many rooms does this schedule actually need? Both are interval sweeps. The same computation consolidates CPU-usage windows in monitoring dashboards, merges IP address ranges in firewall rules, and de-duplicates overlapping time ranges in billing.

Mastery Roadmap & Prerequisite Graph

💡 Don't worry if interval sorting or greedy proofs feel unintuitive right now! Sorting turns quadratic comparisons into one linear pass. As you work through the cards, the same three questions repeat: what is the sort key, what single value do I keep, and when do I save it.

Failing to sort intervals by start time: Interval merging fundamentally requires intervals to be sorted by their start coordinates ( $O(N \log N)$ ). Unsorted inputs cannot be merged in a single linear pass.
Overwriting the interval end instead of taking the maximum: When merging curr and next, the new end time is max(curr.end, next.end). Writing curr.end = next.end corrupts intervals where next is fully contained within curr (e.g. [1, 5] and [2, 3]).
Missing the final merged interval: Because intervals are accumulated dynamically, forgetting to commit the last interval to merged drops the final span.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "merge overlapping intervals", "fewest intervals to remove", "how many meetings overlap at once", "can you reach the last index". Each one is solved by sorting first and then making one pass.

CONSTRAINTS & BOUNDS

Up to $10^4$ to $10^5$ intervals or positions. Sorting costs $O(N \log N)$ and the pass costs $O(N)$ . Comparing every pair costs $O(N^2)$ and is too slow.

FAANG PRODUCTION TRAPS & EDGE CASES

Sorting by the wrong key (start for merging, end for choosing the most intervals); < instead of <= when intervals that touch count as overlapping; forgetting to save the last open interval after the loop; replacing the end instead of taking the larger end.

Theory Context•Intervals & Greedy

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

Many algorithmic problems ask questions about overlapping spans:

"Which calendar meetings conflict?" (Interval Merging)
"How many conference rooms are needed at the same time?" (Sweep-Line Concurrency)
"What is the most intervals I can keep without any overlap?" (Earliest Finish Time)
"Can I reach the last index?" (Greedy Furthest Reach) In their raw form, these problems appear to need $O(N^2)$ pairwise comparisons. Sorting removes that cost:

Sorting by start time places every interval that can overlap the open interval directly after it. One left-to-right pass is enough, and the pass keeps one running interval.
Sorting by end time lets a greedy pass keep the interval that ends first, which leaves the most room for the rest.
A greedy pass without a sort keeps one number, such as the furthest index reached, in place of every possible path.

🛫 The Analogy: The Airport Runway Schedule

🔑 Why It Works

After sorting, each element is compared with one running value, so each element is inspected a constant number of times. The sort costs $O(N \log N)$ and the pass costs $O(N)$ .

Visual Blueprint & State Transition Model

Core Invariant Specification

After sorting by start, anything that overlaps the interval I am building is the very next one I will see. I never need to look backwards.

Boundary Model: Sorted Order, One Running Value

Sort first. Then one running value (the open interval, the last kept end, the furthest reach) is enough to decide each next item.

Loop Invariant Termination

Merge: if curr.start <= prev.end: extend prev.end. Schedule: if curr.start >= prev_end: keep curr.

The 2 Mental Models of Intervals & Greedy

Interval merging, scheduling, sweep lines and one-way greedy choices: name the model before coding.

1Merge Intervals

intervals ➔ sort by start time ➔ merge or extend prev.end

Merge Intervals

Spot it when: Overlapping ranges must be combined, gaps between them found, or a new range inserted into a sorted list of ranges.

Mode 1 · Merge Intervals

Python

1	def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
2	"""Interval Merging via chronological start-time sorting.
3	Time: O(N log N) \| Space: O(N)
4	"""
5	if not intervals:
6	return []
7
8	# 1. Sort by Start Time:
9	# Sorting puts every interval that can overlap the current one directly after it, so one
10	# left-to-right pass is enough: no interval later in the list can start earlier than this one.
11	intervals.sort(key=lambda iv: iv[0])
12	merged: list[list[int]] = [] # merged holds finished, disjoint intervals, in order
13	accumulated = intervals[0] # accumulated is the one interval still open for absorbing overlaps
14
15	for incoming in intervals[1:]:
16	# 2. Absorb or Close the Accumulator:
17	# incoming overlaps accumulated exactly when incoming starts at or before accumulated's end;
18	# touching at one shared point still counts as overlap.
19	if incoming[0] <= accumulated[1]:
20	accumulated[1] = max(accumulated[1], incoming[1]) # Keep the later end: a nested interval must not shrink it
21	else:
22	merged.append(accumulated) # No later interval starts before accumulated ends, so it is finished
23	accumulated = incoming # Start a new accumulator from incoming
24
25	# 3. Flush the Last Accumulator:
26	# The loop only saves accumulated when a later interval closes it, so the final open interval is saved here.
27	merged.append(accumulated)
28	return merged

Gotchas1 of 4

The trap
Gotcha 1: Setting the end to incoming[1] without max
Mistake
```
accumulated[1] = incoming[1]
```
Fix
```
accumulated[1] = max(accumulated[1], incoming[1])
```
What happens: incoming can lie completely inside accumulated. Then incoming[1] is smaller than accumulated[1]. The plain assignment moves the merged end back to incoming[1]. A later interval that overlaps the old end is then saved as a separate interval.
Example: intervals = [[1, 5], [2, 3], [4, 6]]
Mistake: returns [[1, 3], [4, 6]]Fix: returns [[1, 6]]
Gotcha 2: Reusing intervals after the call has changed it
Mistake
```
merged = merge_intervals(intervals)
```
Fix
```
merged = merge_intervals([list(iv) for iv in intervals])
```
What happens: accumulated = intervals[0] does not copy the interval. It points to the caller's own list. So accumulated[1] = ... also changes the caller's first interval. intervals.sort also reorders the caller's list. Pass a copy when the caller still needs the input as it was.
Example: intervals = [[1, 3], [2, 6]], then read intervals again
Mistake: returns [[1, 6], [2, 6]]Fix: returns [[1, 3], [2, 6]]
Gotcha 3: Testing < where touching intervals must merge
Mistake
```
if incoming[0] < accumulated[1]:
```
Fix
```
if incoming[0] <= accumulated[1]:
```
What happens: Merge Intervals (LC 56) counts two intervals that share an end point as overlapping. So [1, 4] and [4, 5] must become [1, 5]. With <, the start 4 is not less than the end 4. The two intervals stay separate.
Example: intervals = [[1, 4], [4, 5]]
Mistake: returns [[1, 4], [4, 5]]Fix: returns [[1, 5]]
Gotcha 4: Not saving the last interval after the loop
Mistake
```
return merged
```
Fix
```
merged.append(accumulated)
return merged
```
What happens: The loop saves accumulated only when a later interval does not overlap it. The last open interval has no later interval. Without the final merged.append(accumulated), it is lost.
Example: intervals = [[1, 3], [2, 6], [8, 10]]
Mistake: returns [[1, 6]]Fix: returns [[1, 6], [8, 10]]

Canonical LeetCode:Merge Intervals (LC 56)Insert Interval (LC 57)Remove Interval (LC 1272)Missing Ranges (LC 163)Teemo Attacking (LC 495)Employee Free Time (LC 759)Meeting Rooms (LC 252)

2Greedy

choices in order ➔ locally best option (exchange argument) ➔ never undone

Greedy (Exchange Argument, Furthest Reach)

Mode 2 · Greedy

Python

1	def can_jump(nums: list[int]) -> bool:
2	"""Jump Game: greedy furthest reach.
3	Time: O(N) \| Space: O(1)
4	"""
5	reach = 0 # Furthest index some run of jumps can land on so far
6
7	for i in range(len(nums)):
8	# 1. Stop When Index i Is Unreachable, Otherwise Extend reach:
9	# An index past reach has no jump landing on it, so it must never extend reach with its own jump;
10	# check that first. Otherwise take the larger of reach and i + nums[i], since a longer reach always
11	# contains every index a shorter one does.
12	if i > reach:
13	return False
14	reach = max(reach, i + nums[i])
15
16	return True # The loop stood on every index, the last one included

Gotchas1 of 3

The trap
Gotcha 1: Updating reach before checking i > reach
Mistake
```
reach = max(reach, i + nums[i])
if i > reach:
    return False
```
Fix
```
if i > reach:
    return False
reach = max(reach, i + nums[i])
```
What happens: An index past reach cannot be stood on. So its jump must never count. Updating first lets that index extend reach with its own jump. Then i > reach is False, and the loop goes on as if index i could be reached.
Example: nums = [3, 2, 1, 0, 4]
Mistake: returns TrueFix: returns False
Gotcha 2: Looping to len(nums) - 1 and skipping the last index
Mistake
```
for i in range(len(nums) - 1):
```
Fix
```
for i in range(len(nums)):
```
What happens: The check i > reach runs only for the indices the loop visits. range(len(nums) - 1) stops before the last index. So the last index is never checked, and the function returns True even when it cannot be reached.
Example: nums = [3, 2, 1, 0, 4]
Mistake: returns TrueFix: returns False
Gotcha 3: Writing reach = i + nums[i] without max
Mistake
```
reach = i + nums[i]
```
Fix
```
reach = max(reach, i + nums[i])
```
What happens: A short jump can come after a long one. Then i + nums[i] is smaller than the current reach. The plain assignment lowers reach, and the loop stops at an index that could be reached.
Example: nums = [4, 1, 0, 0, 0]
Mistake: returns FalseFix: returns True

Built on the mental models above

Interval SchedulingInterval Scheduling (Activity Selection, Greedy by End Time)
Sort by end instead of start, and count or drop intervals instead of merging them.
End-Time GroupsInterval Grouping (Minimum Arrows to Burst Balloons)
Count the groups of intervals that share a point instead of the intervals to remove: shoot at the end of the first interval not yet hit.
Sweep LineSweep Line (Line Sweep)
Break each interval into a start event and an end event, sort the events, and track how many are open.

The Intervals & Greedy Decision Rule

When facing an unseen interval or greedy problem, ask in this order:

Step 1.Does the problem ask to merge overlapping ranges or insert a new range?

Compare curr.start <= prev.end and extend prev.end = max(prev.end, curr.end).

Step 2.Does the problem ask for the minimum intervals to remove or maximum non-overlapping set?

Non-overlapping Intervals (LC 435)Maximum Length of Pair Chain (LC 646)

Sort by end time and greedily retain the earliest ending interval that starts at or after the last kept end.

Step 3.Does the problem track simultaneous active overlaps (rooms, passengers)?

Create +1 (start) and -1 (end) events, sorting end events first at equal timestamps.

Step 4.Does each step offer a choice where the locally best option never has to be undone (jumps, gas stations, partitions)?

➔ Greedy

Prove with an exchange argument that the greedy pick keeps every option another pick would, then take it at every step.

Step 5.Must you pick the fewest points that touch every interval, or split the intervals into the fewest groups that each share a point?

Minimum Number of Arrows to Burst Balloons (LC 452)Maximum Length of Pair Chain (LC 646)

Sort by end and shoot at the end of the first interval not yet hit; an interval that starts at or before that spot is already hit.

Pattern Architecture & Invariant Design Masterclass

One idea runs through every card here: sort first, then keep one running value, and an O(n²) comparison problem becomes O(n).

The invariants to say out loud:

Greedy: "Everything before index i is decided, and one number summarizes what it allows."

How this plays out in actual problems:

🟢 Scenario A: Interval Merging & Absorption (Sort by Start Time)

In interval merging (like Merge Intervals LC 56), we consolidate overlapping blocks into unified continuous spans.
The Rule: Sort intervals by start time. Iterate left-to-right. If incoming[0] <= merged[-1][1], expand the current interval using merged[-1][1] = max(merged[-1][1], incoming[1]). Otherwise, append incoming as a new disjoint block.
The Code: if incoming[0] <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], incoming[1])

🔵 Scenario B: Earliest Finish Time Greedy Scheduling (Sort by End Time)

In non-overlapping interval scheduling (like LC 435 / LC 452), we want to maximize the count of mutually compatible intervals.
The Rule: Sort intervals by end time. Greedily select the interval that finishes earliest. Any subsequent interval whose start < current_end must be removed/skipped.
The Code: if start >= prev_end: prev_end = end; count += 1

💡 The Ultimate Takeaway Decision Rule:
When analyzing an interval or sequence query problem, ask: "Are we merging overlapping spans, scheduling non-overlapping intervals, counting overlaps, or making a one-way choice?"

Consolidating Overlapping Ranges ➔ Sort by start time x[0], sequential absorption ( $O(N \log N)$ ).

Maximizing Non-Overlapping / Min Removals ➔ Sort by end time x[1], greedy earliest finish selection ( $O(N \log N)$ ).

Concurrent Resource Peak (Meeting Rooms II) ➔ Chronological sweep-line boundary events (t, +1) & (t, -1) ( $O(N \log N)$ ).

One-way choice with a proof ➔ Greedy with a single running value, such as reach ( $O(N)$ ).

📦 1. Interval Merge & Absorption (LC 56 & 57)

Mental Model: Sort intervals by start time. After sorting, an interval that overlaps anything already merged must overlap the block being built, merged[-1], so earlier blocks are never checked again.
Code: see the Merge Intervals card.

⏱️ 2. Earliest Finish Time Greedy Scheduling (LC 435 & 452)

Mental Model: To leave maximal room for subsequent intervals, always pick the interval that finishes earliest. Sorting by end time guarantees optimal greedy choice.
LC 435 vs. LC 452: In Non-overlapping Intervals (LC 435), intervals that only touch do not overlap, so the blueprint keeps an interval when start >= prev_end. In Minimum Number of Arrows to Burst Balloons (LC 452), balloons that touch are burst by the same arrow, so a new arrow is needed only when start > prev_end.
Code: see the Interval Scheduling card.

📈 3. Sweep-Line Concurrency & Meeting Rooms II (LC 253)

Mental Model: Decompose intervals into discrete point events: +1 room at start time, -1 room at end time. Sort events chronologically.
Code: see the Sweep Line card.

Understanding Invariants: Interval Sweeps & Greedy Running Values

After sorting by start, anything that overlaps the interval I am building is the very next one I will see.

Interval sweeps sort chronologically to turn quadratic pairwise checks into single O(N) passes, and greedy passes keep one running value that summarizes everything already decided.

Interval Overlap Absorption Invariant

Condition: If incoming[0] <= merged[-1][1]

Action: merged[-1][1] = max(merged[-1][1], incoming[1])

Because intervals are sorted by start, overlapping intervals must be adjacent and can be absorbed into the running block.

Earliest Finish Time Invariant

Condition: If start >= prev_end

Action: prev_end = end; count += 1

Keeping the interval that ends earliest leaves the most room for every interval that comes after it.

Common Questions

"Do [1, 3] and [3, 5] overlap? Which character in my code decides that?"

It depends on the problem, and you must ask before you write code. If intervals that share an endpoint count as overlapping (Merge Intervals), the test is incoming[0] <= merged[-1][1]. The <= merges them. If touching intervals do not count as overlapping (Non-overlapping Intervals), the test is start >= prev_end to keep one. The only difference is one character, < or <=, and it changes the answer.

Coach discussion points

1.
"Do [1,3] and [3,5] overlap? Which character in your code decides that, and what happens if I want the other behaviour?" — Tests whether the convention was a deliberate decision or an accident. Candidates who ask this before coding score highest.
2.
"Your merge loop has an emit inside it. Run me through [[1,4]] — a single interval — line by line." — Discovers the missing final flush by tracing rather than by being told. The cheapest possible test, and the one most solutions fail.
3.
"Same list of meetings, but now I ask how many rooms I need instead of which blocks are busy. What changes about your approach, and why isn't merging enough?" — Separates "the intervals touch" from "how many are simultaneously live", which is the single most common conflation in this pattern.

Complexity analysis

Production Systems Deployment & Motivation

Mastery Roadmap & Prerequisite Graph

Failing to sort intervals by start time: Interval merging fundamentally requires intervals to be sorted by their start coordinates ( $O(N \log N)$ ). Unsorted inputs cannot be merged in a single linear pass.
Overwriting the interval end instead of taking the maximum: When merging curr and next, the new end time is max(curr.end, next.end). Writing curr.end = next.end corrupts intervals where next is fully contained within curr (e.g. [1, 5] and [2, 3]).
Missing the final merged interval: Because intervals are accumulated dynamically, forgetting to commit the last interval to merged drops the final span.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

Up to $10^4$ to $10^5$ intervals or positions. Sorting costs $O(N \log N)$ and the pass costs $O(N)$ . Comparing every pair costs $O(N^2)$ and is too slow.

FAANG PRODUCTION TRAPS & EDGE CASES

Theory Context•Intervals & Greedy

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

Many algorithmic problems ask questions about overlapping spans:

"Which calendar meetings conflict?" (Interval Merging)
"How many conference rooms are needed at the same time?" (Sweep-Line Concurrency)
"What is the most intervals I can keep without any overlap?" (Earliest Finish Time)
"Can I reach the last index?" (Greedy Furthest Reach) In their raw form, these problems appear to need $O(N^2)$ pairwise comparisons. Sorting removes that cost:

Sorting by start time places every interval that can overlap the open interval directly after it. One left-to-right pass is enough, and the pass keeps one running interval.
Sorting by end time lets a greedy pass keep the interval that ends first, which leaves the most room for the rest.
A greedy pass without a sort keeps one number, such as the furthest index reached, in place of every possible path.

🛫 The Analogy: The Airport Runway Schedule

🔑 Why It Works

After sorting, each element is compared with one running value, so each element is inspected a constant number of times. The sort costs $O(N \log N)$ and the pass costs $O(N)$ .

Visual Blueprint & State Transition Model

Core Invariant Specification

After sorting by start, anything that overlaps the interval I am building is the very next one I will see. I never need to look backwards.

Boundary Model: Sorted Order, One Running Value

Sort first. Then one running value (the open interval, the last kept end, the furthest reach) is enough to decide each next item.

Loop Invariant Termination

Merge: if curr.start <= prev.end: extend prev.end. Schedule: if curr.start >= prev_end: keep curr.

The 2 Mental Models of Intervals & Greedy

Interval merging, scheduling, sweep lines and one-way greedy choices: name the model before coding.

1Merge Intervals

intervals ➔ sort by start time ➔ merge or extend prev.end

Merge Intervals

Spot it when: Overlapping ranges must be combined, gaps between them found, or a new range inserted into a sorted list of ranges.

Mode 1 · Merge Intervals

Python

1	def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
2	"""Interval Merging via chronological start-time sorting.
3	Time: O(N log N) \| Space: O(N)
4	"""
5	if not intervals:
6	return []
7
8	# 1. Sort by Start Time:
9	# Sorting puts every interval that can overlap the current one directly after it, so one
10	# left-to-right pass is enough: no interval later in the list can start earlier than this one.
11	intervals.sort(key=lambda iv: iv[0])
12	merged: list[list[int]] = [] # merged holds finished, disjoint intervals, in order
13	accumulated = intervals[0] # accumulated is the one interval still open for absorbing overlaps
14
15	for incoming in intervals[1:]:
16	# 2. Absorb or Close the Accumulator:
17	# incoming overlaps accumulated exactly when incoming starts at or before accumulated's end;
18	# touching at one shared point still counts as overlap.
19	if incoming[0] <= accumulated[1]:
20	accumulated[1] = max(accumulated[1], incoming[1]) # Keep the later end: a nested interval must not shrink it
21	else:
22	merged.append(accumulated) # No later interval starts before accumulated ends, so it is finished
23	accumulated = incoming # Start a new accumulator from incoming
24
25	# 3. Flush the Last Accumulator:
26	# The loop only saves accumulated when a later interval closes it, so the final open interval is saved here.
27	merged.append(accumulated)
28	return merged

Gotchas1 of 4

The trap
Gotcha 1: Setting the end to incoming[1] without max
Mistake
```
accumulated[1] = incoming[1]
```
Fix
```
accumulated[1] = max(accumulated[1], incoming[1])
```
What happens: incoming can lie completely inside accumulated. Then incoming[1] is smaller than accumulated[1]. The plain assignment moves the merged end back to incoming[1]. A later interval that overlaps the old end is then saved as a separate interval.
Example: intervals = [[1, 5], [2, 3], [4, 6]]
Mistake: returns [[1, 3], [4, 6]]Fix: returns [[1, 6]]
Gotcha 2: Reusing intervals after the call has changed it
Mistake
```
merged = merge_intervals(intervals)
```
Fix
```
merged = merge_intervals([list(iv) for iv in intervals])
```
What happens: accumulated = intervals[0] does not copy the interval. It points to the caller's own list. So accumulated[1] = ... also changes the caller's first interval. intervals.sort also reorders the caller's list. Pass a copy when the caller still needs the input as it was.
Example: intervals = [[1, 3], [2, 6]], then read intervals again
Mistake: returns [[1, 6], [2, 6]]Fix: returns [[1, 3], [2, 6]]
Gotcha 3: Testing < where touching intervals must merge
Mistake
```
if incoming[0] < accumulated[1]:
```
Fix
```
if incoming[0] <= accumulated[1]:
```
What happens: Merge Intervals (LC 56) counts two intervals that share an end point as overlapping. So [1, 4] and [4, 5] must become [1, 5]. With <, the start 4 is not less than the end 4. The two intervals stay separate.
Example: intervals = [[1, 4], [4, 5]]
Mistake: returns [[1, 4], [4, 5]]Fix: returns [[1, 5]]
Gotcha 4: Not saving the last interval after the loop
Mistake
```
return merged
```
Fix
```
merged.append(accumulated)
return merged
```
What happens: The loop saves accumulated only when a later interval does not overlap it. The last open interval has no later interval. Without the final merged.append(accumulated), it is lost.
Example: intervals = [[1, 3], [2, 6], [8, 10]]
Mistake: returns [[1, 6]]Fix: returns [[1, 6], [8, 10]]

Canonical LeetCode:Merge Intervals (LC 56)Insert Interval (LC 57)Remove Interval (LC 1272)Missing Ranges (LC 163)Teemo Attacking (LC 495)Employee Free Time (LC 759)Meeting Rooms (LC 252)

2Greedy

choices in order ➔ locally best option (exchange argument) ➔ never undone

Greedy (Exchange Argument, Furthest Reach)

Mode 2 · Greedy

Python

1	def can_jump(nums: list[int]) -> bool:
2	"""Jump Game: greedy furthest reach.
3	Time: O(N) \| Space: O(1)
4	"""
5	reach = 0 # Furthest index some run of jumps can land on so far
6
7	for i in range(len(nums)):
8	# 1. Stop When Index i Is Unreachable, Otherwise Extend reach:
9	# An index past reach has no jump landing on it, so it must never extend reach with its own jump;
10	# check that first. Otherwise take the larger of reach and i + nums[i], since a longer reach always
11	# contains every index a shorter one does.
12	if i > reach:
13	return False
14	reach = max(reach, i + nums[i])
15
16	return True # The loop stood on every index, the last one included

Gotchas1 of 3

The trap
Gotcha 1: Updating reach before checking i > reach
Mistake
```
reach = max(reach, i + nums[i])
if i > reach:
    return False
```
Fix
```
if i > reach:
    return False
reach = max(reach, i + nums[i])
```
What happens: An index past reach cannot be stood on. So its jump must never count. Updating first lets that index extend reach with its own jump. Then i > reach is False, and the loop goes on as if index i could be reached.
Example: nums = [3, 2, 1, 0, 4]
Mistake: returns TrueFix: returns False
Gotcha 2: Looping to len(nums) - 1 and skipping the last index
Mistake
```
for i in range(len(nums) - 1):
```
Fix
```
for i in range(len(nums)):
```
What happens: The check i > reach runs only for the indices the loop visits. range(len(nums) - 1) stops before the last index. So the last index is never checked, and the function returns True even when it cannot be reached.
Example: nums = [3, 2, 1, 0, 4]
Mistake: returns TrueFix: returns False
Gotcha 3: Writing reach = i + nums[i] without max
Mistake
```
reach = i + nums[i]
```
Fix
```
reach = max(reach, i + nums[i])
```
What happens: A short jump can come after a long one. Then i + nums[i] is smaller than the current reach. The plain assignment lowers reach, and the loop stops at an index that could be reached.
Example: nums = [4, 1, 0, 0, 0]
Mistake: returns FalseFix: returns True

Built on the mental models above

Interval SchedulingInterval Scheduling (Activity Selection, Greedy by End Time)
Sort by end instead of start, and count or drop intervals instead of merging them.
End-Time GroupsInterval Grouping (Minimum Arrows to Burst Balloons)
Count the groups of intervals that share a point instead of the intervals to remove: shoot at the end of the first interval not yet hit.
Sweep LineSweep Line (Line Sweep)
Break each interval into a start event and an end event, sort the events, and track how many are open.

The Intervals & Greedy Decision Rule

When facing an unseen interval or greedy problem, ask in this order:

Step 1.Does the problem ask to merge overlapping ranges or insert a new range?

Compare curr.start <= prev.end and extend prev.end = max(prev.end, curr.end).

Step 2.Does the problem ask for the minimum intervals to remove or maximum non-overlapping set?

Non-overlapping Intervals (LC 435)Maximum Length of Pair Chain (LC 646)

Sort by end time and greedily retain the earliest ending interval that starts at or after the last kept end.

Step 3.Does the problem track simultaneous active overlaps (rooms, passengers)?

Create +1 (start) and -1 (end) events, sorting end events first at equal timestamps.

Step 4.Does each step offer a choice where the locally best option never has to be undone (jumps, gas stations, partitions)?

➔ Greedy

Prove with an exchange argument that the greedy pick keeps every option another pick would, then take it at every step.

Step 5.Must you pick the fewest points that touch every interval, or split the intervals into the fewest groups that each share a point?

Minimum Number of Arrows to Burst Balloons (LC 452)Maximum Length of Pair Chain (LC 646)

Sort by end and shoot at the end of the first interval not yet hit; an interval that starts at or before that spot is already hit.

Pattern Architecture & Invariant Design Masterclass

One idea runs through every card here: sort first, then keep one running value, and an O(n²) comparison problem becomes O(n).

The invariants to say out loud:

Greedy: "Everything before index i is decided, and one number summarizes what it allows."

How this plays out in actual problems:

🟢 Scenario A: Interval Merging & Absorption (Sort by Start Time)

In interval merging (like Merge Intervals LC 56), we consolidate overlapping blocks into unified continuous spans.
The Rule: Sort intervals by start time. Iterate left-to-right. If incoming[0] <= merged[-1][1], expand the current interval using merged[-1][1] = max(merged[-1][1], incoming[1]). Otherwise, append incoming as a new disjoint block.
The Code: if incoming[0] <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], incoming[1])

🔵 Scenario B: Earliest Finish Time Greedy Scheduling (Sort by End Time)

In non-overlapping interval scheduling (like LC 435 / LC 452), we want to maximize the count of mutually compatible intervals.
The Rule: Sort intervals by end time. Greedily select the interval that finishes earliest. Any subsequent interval whose start < current_end must be removed/skipped.
The Code: if start >= prev_end: prev_end = end; count += 1

💡 The Ultimate Takeaway Decision Rule:
When analyzing an interval or sequence query problem, ask: "Are we merging overlapping spans, scheduling non-overlapping intervals, counting overlaps, or making a one-way choice?"

Consolidating Overlapping Ranges ➔ Sort by start time x[0], sequential absorption ( $O(N \log N)$ ).

Maximizing Non-Overlapping / Min Removals ➔ Sort by end time x[1], greedy earliest finish selection ( $O(N \log N)$ ).

Concurrent Resource Peak (Meeting Rooms II) ➔ Chronological sweep-line boundary events (t, +1) & (t, -1) ( $O(N \log N)$ ).

One-way choice with a proof ➔ Greedy with a single running value, such as reach ( $O(N)$ ).

📦 1. Interval Merge & Absorption (LC 56 & 57)

Mental Model: Sort intervals by start time. After sorting, an interval that overlaps anything already merged must overlap the block being built, merged[-1], so earlier blocks are never checked again.
Code: see the Merge Intervals card.

⏱️ 2. Earliest Finish Time Greedy Scheduling (LC 435 & 452)

Mental Model: To leave maximal room for subsequent intervals, always pick the interval that finishes earliest. Sorting by end time guarantees optimal greedy choice.
LC 435 vs. LC 452: In Non-overlapping Intervals (LC 435), intervals that only touch do not overlap, so the blueprint keeps an interval when start >= prev_end. In Minimum Number of Arrows to Burst Balloons (LC 452), balloons that touch are burst by the same arrow, so a new arrow is needed only when start > prev_end.
Code: see the Interval Scheduling card.

📈 3. Sweep-Line Concurrency & Meeting Rooms II (LC 253)

Mental Model: Decompose intervals into discrete point events: +1 room at start time, -1 room at end time. Sort events chronologically.
Code: see the Sweep Line card.

Understanding Invariants: Interval Sweeps & Greedy Running Values

After sorting by start, anything that overlaps the interval I am building is the very next one I will see.

Interval sweeps sort chronologically to turn quadratic pairwise checks into single O(N) passes, and greedy passes keep one running value that summarizes everything already decided.

Interval Overlap Absorption Invariant

Condition: If incoming[0] <= merged[-1][1]

Action: merged[-1][1] = max(merged[-1][1], incoming[1])

Because intervals are sorted by start, overlapping intervals must be adjacent and can be absorbed into the running block.

Earliest Finish Time Invariant

Condition: If start >= prev_end

Action: prev_end = end; count += 1

Keeping the interval that ends earliest leaves the most room for every interval that comes after it.

Common Questions

"Do [1, 3] and [3, 5] overlap? Which character in my code decides that?"

It depends on the problem, and you must ask before you write code. If intervals that share an endpoint count as overlapping (Merge Intervals), the test is incoming[0] <= merged[-1][1]. The <= merges them. If touching intervals do not count as overlapping (Non-overlapping Intervals), the test is start >= prev_end to keep one. The only difference is one character, < or <=, and it changes the answer.

Coach discussion points

1.
"Do [1,3] and [3,5] overlap? Which character in your code decides that, and what happens if I want the other behaviour?" — Tests whether the convention was a deliberate decision or an accident. Candidates who ask this before coding score highest.
2.
"Your merge loop has an emit inside it. Run me through [[1,4]] — a single interval — line by line." — Discovers the missing final flush by tracing rather than by being told. The cheapest possible test, and the one most solutions fail.
3.
"Same list of meetings, but now I ask how many rooms I need instead of which blocks are busy. What changes about your approach, and why isn't merging enough?" — Separates "the intervals touch" from "how many are simultaneously live", which is the single most common conflation in this pattern.

Complexity analysis

Production Systems Deployment & Motivation

Mastery Roadmap & Prerequisite Graph

Failing to sort intervals by start time: Interval merging fundamentally requires intervals to be sorted by their start coordinates ( $O(N \log N)$ ). Unsorted inputs cannot be merged in a single linear pass.
Overwriting the interval end instead of taking the maximum: When merging curr and next, the new end time is max(curr.end, next.end). Writing curr.end = next.end corrupts intervals where next is fully contained within curr (e.g. [1, 5] and [2, 3]).
Missing the final merged interval: Because intervals are accumulated dynamically, forgetting to commit the last interval to merged drops the final span.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

Up to $10^4$ to $10^5$ intervals or positions. Sorting costs $O(N \log N)$ and the pass costs $O(N)$ . Comparing every pair costs $O(N^2)$ and is too slow.

FAANG PRODUCTION TRAPS & EDGE CASES

Theory Context•Intervals & Greedy

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

Many algorithmic problems ask questions about overlapping spans:

"Which calendar meetings conflict?" (Interval Merging)
"How many conference rooms are needed at the same time?" (Sweep-Line Concurrency)
"What is the most intervals I can keep without any overlap?" (Earliest Finish Time)
"Can I reach the last index?" (Greedy Furthest Reach) In their raw form, these problems appear to need $O(N^2)$ pairwise comparisons. Sorting removes that cost:

Sorting by start time places every interval that can overlap the open interval directly after it. One left-to-right pass is enough, and the pass keeps one running interval.
Sorting by end time lets a greedy pass keep the interval that ends first, which leaves the most room for the rest.
A greedy pass without a sort keeps one number, such as the furthest index reached, in place of every possible path.

🛫 The Analogy: The Airport Runway Schedule

🔑 Why It Works

After sorting, each element is compared with one running value, so each element is inspected a constant number of times. The sort costs $O(N \log N)$ and the pass costs $O(N)$ .

Visual Blueprint & State Transition Model

Core Invariant Specification

After sorting by start, anything that overlaps the interval I am building is the very next one I will see. I never need to look backwards.

Boundary Model: Sorted Order, One Running Value

Sort first. Then one running value (the open interval, the last kept end, the furthest reach) is enough to decide each next item.

Loop Invariant Termination

Merge: if curr.start <= prev.end: extend prev.end. Schedule: if curr.start >= prev_end: keep curr.

The 2 Mental Models of Intervals & Greedy

Interval merging, scheduling, sweep lines and one-way greedy choices: name the model before coding.

1Merge Intervals

intervals ➔ sort by start time ➔ merge or extend prev.end

Merge Intervals

Spot it when: Overlapping ranges must be combined, gaps between them found, or a new range inserted into a sorted list of ranges.

Mode 1 · Merge Intervals

Python

1	def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
2	"""Interval Merging via chronological start-time sorting.
3	Time: O(N log N) \| Space: O(N)
4	"""
5	if not intervals:
6	return []
7
8	# 1. Sort by Start Time:
9	# Sorting puts every interval that can overlap the current one directly after it, so one
10	# left-to-right pass is enough: no interval later in the list can start earlier than this one.
11	intervals.sort(key=lambda iv: iv[0])
12	merged: list[list[int]] = [] # merged holds finished, disjoint intervals, in order
13	accumulated = intervals[0] # accumulated is the one interval still open for absorbing overlaps
14
15	for incoming in intervals[1:]:
16	# 2. Absorb or Close the Accumulator:
17	# incoming overlaps accumulated exactly when incoming starts at or before accumulated's end;
18	# touching at one shared point still counts as overlap.
19	if incoming[0] <= accumulated[1]:
20	accumulated[1] = max(accumulated[1], incoming[1]) # Keep the later end: a nested interval must not shrink it
21	else:
22	merged.append(accumulated) # No later interval starts before accumulated ends, so it is finished
23	accumulated = incoming # Start a new accumulator from incoming
24
25	# 3. Flush the Last Accumulator:
26	# The loop only saves accumulated when a later interval closes it, so the final open interval is saved here.
27	merged.append(accumulated)
28	return merged

Gotchas1 of 4

The trap
Gotcha 1: Setting the end to incoming[1] without max
Mistake
```
accumulated[1] = incoming[1]
```
Fix
```
accumulated[1] = max(accumulated[1], incoming[1])
```
What happens: incoming can lie completely inside accumulated. Then incoming[1] is smaller than accumulated[1]. The plain assignment moves the merged end back to incoming[1]. A later interval that overlaps the old end is then saved as a separate interval.
Example: intervals = [[1, 5], [2, 3], [4, 6]]
Mistake: returns [[1, 3], [4, 6]]Fix: returns [[1, 6]]
Gotcha 2: Reusing intervals after the call has changed it
Mistake
```
merged = merge_intervals(intervals)
```
Fix
```
merged = merge_intervals([list(iv) for iv in intervals])
```
What happens: accumulated = intervals[0] does not copy the interval. It points to the caller's own list. So accumulated[1] = ... also changes the caller's first interval. intervals.sort also reorders the caller's list. Pass a copy when the caller still needs the input as it was.
Example: intervals = [[1, 3], [2, 6]], then read intervals again
Mistake: returns [[1, 6], [2, 6]]Fix: returns [[1, 3], [2, 6]]
Gotcha 3: Testing < where touching intervals must merge
Mistake
```
if incoming[0] < accumulated[1]:
```
Fix
```
if incoming[0] <= accumulated[1]:
```
What happens: Merge Intervals (LC 56) counts two intervals that share an end point as overlapping. So [1, 4] and [4, 5] must become [1, 5]. With <, the start 4 is not less than the end 4. The two intervals stay separate.
Example: intervals = [[1, 4], [4, 5]]
Mistake: returns [[1, 4], [4, 5]]Fix: returns [[1, 5]]
Gotcha 4: Not saving the last interval after the loop
Mistake
```
return merged
```
Fix
```
merged.append(accumulated)
return merged
```
What happens: The loop saves accumulated only when a later interval does not overlap it. The last open interval has no later interval. Without the final merged.append(accumulated), it is lost.
Example: intervals = [[1, 3], [2, 6], [8, 10]]
Mistake: returns [[1, 6]]Fix: returns [[1, 6], [8, 10]]

Canonical LeetCode:Merge Intervals (LC 56)Insert Interval (LC 57)Remove Interval (LC 1272)Missing Ranges (LC 163)Teemo Attacking (LC 495)Employee Free Time (LC 759)Meeting Rooms (LC 252)

2Greedy

choices in order ➔ locally best option (exchange argument) ➔ never undone

Greedy (Exchange Argument, Furthest Reach)

Mode 2 · Greedy

Python

1	def can_jump(nums: list[int]) -> bool:
2	"""Jump Game: greedy furthest reach.
3	Time: O(N) \| Space: O(1)
4	"""
5	reach = 0 # Furthest index some run of jumps can land on so far
6
7	for i in range(len(nums)):
8	# 1. Stop When Index i Is Unreachable, Otherwise Extend reach:
9	# An index past reach has no jump landing on it, so it must never extend reach with its own jump;
10	# check that first. Otherwise take the larger of reach and i + nums[i], since a longer reach always
11	# contains every index a shorter one does.
12	if i > reach:
13	return False
14	reach = max(reach, i + nums[i])
15
16	return True # The loop stood on every index, the last one included

Gotchas1 of 3

The trap
Gotcha 1: Updating reach before checking i > reach
Mistake
```
reach = max(reach, i + nums[i])
if i > reach:
    return False
```
Fix
```
if i > reach:
    return False
reach = max(reach, i + nums[i])
```
What happens: An index past reach cannot be stood on. So its jump must never count. Updating first lets that index extend reach with its own jump. Then i > reach is False, and the loop goes on as if index i could be reached.
Example: nums = [3, 2, 1, 0, 4]
Mistake: returns TrueFix: returns False
Gotcha 2: Looping to len(nums) - 1 and skipping the last index
Mistake
```
for i in range(len(nums) - 1):
```
Fix
```
for i in range(len(nums)):
```
What happens: The check i > reach runs only for the indices the loop visits. range(len(nums) - 1) stops before the last index. So the last index is never checked, and the function returns True even when it cannot be reached.
Example: nums = [3, 2, 1, 0, 4]
Mistake: returns TrueFix: returns False
Gotcha 3: Writing reach = i + nums[i] without max
Mistake
```
reach = i + nums[i]
```
Fix
```
reach = max(reach, i + nums[i])
```
What happens: A short jump can come after a long one. Then i + nums[i] is smaller than the current reach. The plain assignment lowers reach, and the loop stops at an index that could be reached.
Example: nums = [4, 1, 0, 0, 0]
Mistake: returns FalseFix: returns True

Built on the mental models above

Interval SchedulingInterval Scheduling (Activity Selection, Greedy by End Time)
Sort by end instead of start, and count or drop intervals instead of merging them.
End-Time GroupsInterval Grouping (Minimum Arrows to Burst Balloons)
Count the groups of intervals that share a point instead of the intervals to remove: shoot at the end of the first interval not yet hit.
Sweep LineSweep Line (Line Sweep)
Break each interval into a start event and an end event, sort the events, and track how many are open.

The Intervals & Greedy Decision Rule

When facing an unseen interval or greedy problem, ask in this order:

Step 1.Does the problem ask to merge overlapping ranges or insert a new range?

Compare curr.start <= prev.end and extend prev.end = max(prev.end, curr.end).

Step 2.Does the problem ask for the minimum intervals to remove or maximum non-overlapping set?

Non-overlapping Intervals (LC 435)Maximum Length of Pair Chain (LC 646)

Sort by end time and greedily retain the earliest ending interval that starts at or after the last kept end.

Step 3.Does the problem track simultaneous active overlaps (rooms, passengers)?

Create +1 (start) and -1 (end) events, sorting end events first at equal timestamps.

Step 4.Does each step offer a choice where the locally best option never has to be undone (jumps, gas stations, partitions)?

➔ Greedy

Prove with an exchange argument that the greedy pick keeps every option another pick would, then take it at every step.

Step 5.Must you pick the fewest points that touch every interval, or split the intervals into the fewest groups that each share a point?