Intervals - Employee Free Time
Given the following schedule input, what is the output of the sweep line Employee Free Time algorithm?
schedule = [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]]
Given the following schedule input, what is the output of the sweep line Employee Free Time algorithm? schedule = [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]]
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Sort all interval endpoints with start=+1, end=-1
Events: (1,+1),(2,+1),(2,+1),(3,-1),(4,-1),(5,-1),(6,+1),(7,-1),(9,+1),(12,-1)Step 2: Sweep line active count and track free intervals when active=0
Active intervals count changes: 0->1 at 1, 1->3 at 2, 3->2 at 3, 2->1 at 4, 1->0 at 5 (free start), 0->1 at 6 (free end), 1->0 at 7 (free start), 0->1 at 9 (free end), 1->0 at 12Final Answer:
Option A -> Option AQuick Check:
Free intervals are [5,6] and [7,9] [OK]
Quick Trick: Track active count changes to find free intervals [OK]
Common Mistakes:
MISTAKES- Misordering events or missing free intervals between close intervals
Trap Explanation:
PITFALL- Candidates often miss that end events come before start events at same time, causing off-by-one errors.
Interviewer Note:
CONTEXT- Tests ability to mentally execute sweep line on typical input.
Master "Employee Free Time" in Intervals
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Intervals Quizzes