Intervals - Minimum Number of Platforms Required
Given arrivals = [900, 940, 950] and departures = [910, 1200, 1120], what is the minimum number of platforms required using the sweep line algorithm?
Given arrivals = [900, 940, 950] and departures = [910, 1200, 1120], what is the minimum number of platforms required using the sweep line algorithm?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Create events and sort
Events: (900,1), (910,-1), (940,1), (950,1), (1120,-1), (1200,-1). Sorted by time and event type.Step 2: Sweep line count
Count platforms: at 900 arrival -> 1, 910 departure -> 0, 940 arrival -> 1, 950 arrival -> 2, 1120 departure -> 1, 1200 departure -> 0. Max is 2.Final Answer:
Option B -> Option BQuick Check:
Maximum concurrent trains = 2 [OK]
Quick Trick: Sort events, count concurrency -> max platforms [OK]
Common Mistakes:
MISTAKES- Not sorting departures before arrivals at same time, overcounting platforms
Trap Explanation:
PITFALL- Candidates often forget to sort departures before arrivals at same time, inflating count.
Interviewer Note:
CONTEXT- Tests ability to trace sweep line algorithm on typical input.
Master "Minimum Number of Platforms Required" in Intervals
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Intervals Quizzes