Which of the following problems CANNOT be solved optimally using the Two City Scheduling greedy pattern (sorting by cost difference)?

easy🔍 Pattern Recognition Q2 of Q15

Greedy Algorithms - Two City Scheduling

AAssign n people to two cities with no restriction on group sizes

BAssign 2n people to two cities minimizing total cost with equal group sizes

CAssign 2n people to two cities with equal group sizes and different costs per person

DAssign 2n people to two cities with equal group sizes minimizing total cost

Step-by-Step Solution

Solution:

Step 1: Analyze problem constraints
Two City Scheduling requires exactly n people per city and cost differences per person.
Step 2: Identify anti-pattern
Assign 2n people to two cities minimizing total cost with equal group sizes states minimizing total cost with equal group sizes but does not specify cost differences or balanced assignment constraints clearly, making greedy sorting by cost difference inapplicable.
Final Answer:
Option B -> Option B
Quick Check:
Only problems with balanced assignments and cost differences fit the pattern [OK]

Quick Trick: Balanced assignment with cost difference is key [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often overlook the balanced assignment constraint, picking greedy incorrectly.

Interviewer Note:

CONTEXT

Master "Two City Scheduling" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Greedy Algorithms Quizzes