Greedy Algorithms - Two City Scheduling
What is the time complexity of the optimal greedy solution for Two City Scheduling that sorts by cost difference and assigns people in a single pass?
What is the time complexity of the optimal greedy solution for Two City Scheduling that sorts by cost difference and assigns people in a single pass?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Solution:
Step 1: Identify sorting cost
Sorting 2n people by cost difference takes O(n log n) time.Step 2: Identify assignment cost
Assigning people in a single pass is O(n).Final Answer:
Option D -> Option DQuick Check:
Sorting dominates, total complexity is O(n log n) [OK]
Quick Trick: Sorting dominates time complexity [OK]
Common Mistakes:
MISTAKES- Assuming assignment is nested loop causing O(n^2)
- Ignoring sorting cost and claiming O(n)
- Confusing space complexity with time complexity
Trap Explanation:
PITFALL- Option B looks right but omits the assignment step; option D correctly includes both sorting and assignment.
Interviewer Note:
CONTEXT- Checks understanding of sorting cost and linear assignment in greedy algorithms.
Master "Two City Scheduling" in Greedy Algorithms
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Greedy Algorithms Quizzes