Greedy Algorithms - Minimum Platforms (Train Stations)
What is the time complexity of the min-heap based algorithm for finding the minimum number of platforms required given n trains?
What is the time complexity of the min-heap based algorithm for finding the minimum number of platforms required given n trains?
medium🪤 Complexity Trap Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Sorting trains by arrival time
Sorting n trains takes O(n log n) time.Step 2: Processing each train with heap operations
Each train causes at most one push and pop on the heap, each O(log n), total O(n log n).Final Answer:
Option D -> Option DQuick Check:
Sorting + heap operations dominate -> O(n log n) [OK]
Quick Trick: Sorting + heap push/pop -> O(n log n) [OK]
Common Mistakes:
MISTAKES- Assuming O(n^2) due to nested loops
- Thinking heap operations are O(1)
- Confusing with linear scan complexity
Trap Explanation:
PITFALL- Candidates often mistake heap operations as constant time, underestimating complexity.
Interviewer Note:
CONTEXT- Tests understanding of sorting and heap operation costs.
Master "Minimum Platforms (Train Stations)" in Greedy Algorithms
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Greedy Algorithms Quizzes