Two City Scheduling

▶

Steps

setup

Initial Input Array

We start with the original array of costs for each person to travel to city A and city B.

💡 Seeing the raw input helps understand what data the algorithm processes.

Line:

costs = [[10,20],[30,200],[400,50],[30,20]]

💡 The problem involves choosing city assignments based on these costs.

setup

Sort by Cost Difference (costA - costB)

We sort the array by the difference between cost to city A and cost to city B for each person.

💡 Sorting by cost difference helps prioritize sending people to the city where they save the most money.

Line:

costs.sort(key=lambda x: x[0] - x[1])

💡 Sorting arranges people so those cheaper for city A come first, and those cheaper for city B come last.

setup

Calculate Halfway Point n

Calculate n as half the number of people, which determines how many go to city A.

💡 Knowing n lets us split the sorted list into two groups for city assignments.

Line:

n = len(costs) // 2

💡 We must send exactly n people to each city for balanced assignment.

traverse

Start Assigning Person 0

Assign person at index 0 to city A because 0 < n (2). Add costA (10) to total.

💡 Assigning the first half to city A follows the greedy strategy after sorting.

Line:

if i < n:
    total += cost[0]

💡 People with lowest cost difference go to city A to minimize total cost.

traverse

Assign Person 1 to City A

Assign person at index 1 to city A because 1 < n (2). Add costA (30) to total.

💡 Continuing to assign first half to city A accumulates cost efficiently.

Line:

if i < n:
    total += cost[0]

💡 Assigning person 1 to city A keeps total cost minimal.

traverse

Assign Person 2 to City B

Assign person at index 2 to city B because 2 >= n (2). Add costB (50) to total.

💡 After first half assigned to city A, remaining go to city B to balance assignments.

Line:

else:
    total += cost[1]

💡 Assigning person 2 to city B minimizes total cost given sorting.

traverse

Assign Person 3 to City B

Assign person at index 3 to city B because 3 >= n (2). Add costB (20) to total.

💡 Final person assigned to city B completes the balanced assignment.

Line:

else:
    total += cost[1]

💡 Assigning person 3 to city B finalizes the minimal total cost.

traverse

End of Loop - All Assigned

All people have been assigned to cities; total cost is accumulated as 110.

💡 Loop completion means all decisions are made and total cost is final.

Line:

for i, cost in enumerate(costs):
    ...
return total

💡 The greedy assignment after sorting yields the minimal total cost.

reconstruct

Return Total Cost

Return the total cost of 110 as the minimal cost to send half the people to each city.

💡 Returning the result concludes the algorithm and confirms the minimal cost found.

Line:

return total

💡 The final answer is the sum of optimal assignments.

reconstruct

Final State Summary

Summary of final assignments and total cost: persons 0 and 1 to city A, persons 2 and 3 to city B, total cost 110.

💡 This final view consolidates all assignments and the minimal total cost found.

💡 The greedy approach efficiently balances assignments for minimal cost.

def twoCitySchedCost(costs):  # STEP 1-2
    costs.sort(key=lambda x: x[0] - x[1])  # STEP 2
    n = len(costs) // 2  # STEP 3
    total = 0  # STEP 3
    for i, cost in enumerate(costs):  # STEP 4-7
        if i < n:  # STEP 4-5
            total += cost[0]  # STEP 4-5
        else:  # STEP 6-7
            total += cost[1]  # STEP 6-7
    return total  # STEP 8-9

if __name__ == '__main__':
    costs = [[10,20],[30,200],[400,50],[30,20]]  # STEP 1
    print(twoCitySchedCost(costs))  # STEP 9

📊

Two City Scheduling - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how sorting by cost difference leads to an optimal assignment without trying all combinations.

setup

[10,20]

0

[30,200]

1

[400,50]

2

[30,20]

3

Result: 0

sort

[10,20]

0

[30,20]

1

[400,50]

2

[30,200]

3

Result: 0

calculate

[10,20]

0

[30,20]

1

n

[400,50]

2

[30,200]

3

Result: 0

record

i

[10,20]

0

[30,20]

1

[400,50]

2

[30,200]

3

Result: 10

record

[10,20]

0

i

[30,20]

1

[400,50]

2

[30,200]

3

Result: 40

record

[10,20]

0

[30,20]

1

i

[400,50]

2

[30,200]

3

Result: 90

record

[10,20]

0

[30,20]

1

[400,50]

2

i

[30,200]

3

Result: 110

complete

[10,20]

0

[30,20]

1

[400,50]

2

[30,200]

3

Result: 110

return

[10,20]

0

[30,20]

1

[400,50]

2

[30,200]

3

Result: 110

complete

[10,20]

0

[30,20]

1

n

[400,50]

2

[30,200]

3

Result: 110

Key Takeaways

✓ Sorting by cost difference is the key to the greedy solution.

This insight is hard to see from code alone because the sorting criterion is subtle but crucial.

✓ Assigning the first half to city A and the rest to city B after sorting guarantees minimal total cost.

Visually seeing the split and assignments clarifies why this approach works without exhaustive search.

✓ Each assignment step updates the total cost incrementally, showing how the solution builds up.

Watching cost accumulation step-by-step reveals the impact of each decision.

Practice

1. You have a list of children each with a greed factor and a list of cookies each with a size. You want to assign cookies to children so that each child gets at most one cookie and the cookie size is at least the child's greed factor. Which algorithmic approach guarantees the maximum number of content children?

easy

A. Greedy algorithm by sorting greed factors and cookie sizes, then assigning smallest sufficient cookie to each child

B. Dynamic Programming to try all possible assignments and pick the best

C. Brute force nested loops checking every cookie for every child without sorting

D. Divide and Conquer by splitting children and cookies and merging results

Solution

1. Step 1: Understand problem constraints

   Each child can get at most one cookie, and the cookie must satisfy the child's greed factor.

2. Step 2: Identify optimal approach

   Sorting both greed and cookie arrays allows a greedy assignment from smallest greed to smallest sufficient cookie, ensuring maximum matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy sorting approach is classic for assignment problems [OK]

Hint: Sort both arrays and assign greedily [OK]

Common Mistakes:

• Thinking brute force is needed for optimality
• Assuming DP is required
• Ignoring sorting leads to suboptimal matches

2. You are given an array where each element represents the maximum jump length from that position. You need to determine if you can reach the last index starting from the first index. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Dynamic Programming with bottom-up tabulation to check reachability for each index

B. Breadth-first search using a queue to explore reachable indices level by level

C. Depth-first search exploring all possible jump paths recursively without memoization

D. Greedy algorithm tracking the maximum reachable index while iterating through the array

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if the last index is reachable from the first index using jumps defined by array values.

2. Step 2: Identify optimal approach

   Greedy approach efficiently tracks the furthest reachable index in one pass, guaranteeing O(n) time complexity, unlike exhaustive search or DP which are slower.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy approach is linear and optimal for this problem [OK]

Hint: Greedy tracks max reachable index in one pass [OK]

Common Mistakes:

• Confusing DP with greedy, thinking recursion is needed

3. Given the following code for the Task Scheduler, what is the returned value for leastInterval(['A','A','B'], 2)?

easy

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Initialize frequencies and max-heap

   Tasks: A(2), B(1). Max-heap: [-2, -1].

2. Step 2: Simulate scheduling cycles

   Cycle 1: pop -2 (A), decrement to -1 and store; pop -1 (B), decrement to 0 ignore; cycle=2, heap not empty -> time += n+1=3.
   Cycle 2: pop -1 (A), decrement to 0 ignore; cycle=1, heap empty -> time += cycle=1.
   Total time = 3 + 1 = 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual simulation matches 4 units [OK]

Hint: Count cycles and add idle if heap not empty [OK]

Common Mistakes:

• Off-by-one in cycle count
• Adding n+1 even when heap empty
• Ignoring decrement of counts

4. The following code attempts to solve the Jump Game problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        # Bug: missing check if current index is beyond maxReach
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

medium

A. Line 2: Initialization of maxReach

B. Line 3: for loop header enumerating nums

C. Line 4: Missing check if i > maxReach before updating maxReach

D. Line 6: Checking if maxReach reaches or exceeds last index

Solution

1. Step 1: Understand the missing condition

   The code does not check if the current index i is beyond maxReach, which means it may continue even when stuck.

2. Step 2: Identify the bug line

   Line 4 updates maxReach without verifying if i is reachable, causing false positives on inputs with unreachable indices.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding "if i > maxReach: return False" fixes the bug [OK]

Hint: Check if current index is reachable before updating maxReach [OK]

Common Mistakes:

• Forgetting to check i > maxReach
• Assuming maxReach update alone suffices

5. What is the worst-case time complexity of the BFS-based solution for Jump Game II on an input array of length n?

medium

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(n^3)

Solution

1. Step 1: Identify outer and inner loops

   The BFS processes each index once, but for each index, it may enqueue up to nums[pos] next positions, which can be up to n.

2. Step 2: Analyze nested iteration

   In worst case (e.g., nums[i] = n for all i), inner loop runs O(n) times for each of O(n) indices -> O(n^2) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over n indices and jumps -> O(n^2) [OK]

Hint: Nested loops over n indices and jumps -> O(n^2) [OK]

Common Mistakes:

• Assuming BFS is always O(n)
• Confusing with greedy linear time
• Ignoring inner loop over jump range