1029. Two City Scheduling

1029

MediumGreedy AlgorithmsGreedy interval problemsPattern-guided

Two City Scheduling

Solve LeetCode #1029, “Two City Scheduling.” Read the official prompt once, then return here to turn its requirements into the greedy algorithms pattern.

Open official problem prompt ↗

In plain English

Learn how to translate “Two City Scheduling” into a precise state, transition, and stopping condition before committing to code.

Picture it like this

Treat the prompt like a route on a map: Greedy Algorithms is the map legend, the invariant is your current location marker, and each code step must move you closer to the destination without losing what is already known.

Example

Input: Use the first example in the official prompt
Output: Predict the result before reading the explanation
Why: Trace how the greedy algorithms invariant transforms the input into the required answer.

Constraints

Identify the input shape and required return valueMark the largest constraint before choosing an approachConfirm that O(n log n) is appropriate for that constraint

Pattern lesson

See the pattern, then code

Greedy interval problems

↗

Greedy Algorithms

A locally best action can be justified by an exchange argument or invariant.. The chosen prefix is at least as extendable as any alternative prefix.

New words, made simpleKnow these before the algorithm

Signal: A phrase or constraint in the prompt that points toward Greedy Algorithms.
State: The smallest set of facts the algorithm must remember while it processes the input.
Invariant: The chosen prefix is at least as extendable as any alternative prefix.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Direct simulation or enumeration

Useful for a tiny example, but compare it with the largest constraint before coding.

Follow the wording literally and try every candidate, using it as a correctness baseline.

Time Usually quadratic or exponentialSpace Problem dependent

Best choiceGreedy Algorithms pattern

This is the recommended starting structure; adapt its state and return value to the official prompt.

Maintain this invariant: The chosen prefix is at least as extendable as any alternative prefix.

Time O(n log n)Space O(1) extra

The rule we keep true

Invariant

The chosen prefix is at least as extendable as any alternative prefix.

Why this is correct

Reasoning

The Greedy Algorithms template avoids repeating work by preserving exactly the information needed for the next decision. For “Two City Scheduling,” prove that every update keeps the invariant true and that the final state matches the requested output.

The algorithm in three movesSay these aloud before coding

1Restate the prompt with a tiny hand-made example

Goal: Two City Scheduling

2Name the state maintained by the greedy algorithms pattern

Pattern: Greedy Algorithms

3Trace one complete iteration before writing code

Invariant: The chosen prefix is at least as extendable as any alternative prefix.

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

Prompt0

State1

Choice2

Invariant3

Answer4

1 · ReadLeetCode #1029: Two City Scheduling

2 · AskWhat are the input, output, and largest constraint?

3 · Update stateTopic = Greedy Algorithms; tier = Greedy interval problems

4 · ResultWrite a one-sentence contract and reject approaches that exceed the constraint.

Key takeaway

Move from the raw prompt to a maintained invariant, then to the final answer.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 1Name the pattern operation
Start from the reusable template, but rename the function and parameters to match the official prompt.
2
Lines 1–3Define the state
Locate the variables or data structure that remember everything needed for the next decision.
3
Lines 5Find the transition
This is where the current input changes the maintained state. Say the update aloud before editing it.
4
Lines 7–9Connect state to the answer
Adapt the template’s generic result to the exact return type and success condition in this problem.
5
Lines 1–9Verify the contract
Trace the official example and confirm the promised O(n log n) time and O(1) extra space bounds.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Use the smallest input allowed by the prompt.
Try an input where no candidate or transition succeeds, if the contract permits it.
Try duplicate, equal, empty, boundary, or maximum values relevant to the input type.

Common beginner mistakes

Copying the pattern template without adapting its state to this problem’s return value.
Choosing the pattern from the title alone instead of checking constraints and monotonicity.
Stating a complexity without counting every nested loop, data-structure operation, and recursion level.

Check your understanding

Before coding “Two City Scheduling,” what invariant will you maintain, and which line of the prompt makes that invariant useful?

Two City Scheduling

Two City Scheduling

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Greedy Algorithms