Intervals - Count of Intervals Containing Each Point
Given intervals [[1,4],[2,5],[7,8]] and points [2,5,6], what is the output of the line sweep algorithm counting intervals containing each point?
Given intervals [[1,4],[2,5],[7,8]] and points [2,5,6], what is the output of the line sweep algorithm counting intervals containing each point?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace events in order
Events sorted: (1,+1), (2,+1), (2,0), (5+1=6,-1), (5,0), (7,+1), (8+1=9,-1), (6,0). Process carefully.Step 2: Count active intervals at each point
At point 2: active intervals = 2 (intervals [1,4] and [2,5]). At point 5: active intervals = 1 (only [2,5]). At point 6: active intervals = 0 (no intervals cover 6).Final Answer:
Option A -> Option AQuick Check:
Correct counts for each point after event processing [OK]
Quick Trick: Remember end event at end+1 excludes point at interval end [OK]
Common Mistakes:
MISTAKES- Counting intervals ending exactly at point incorrectly
- Misordering events causing wrong active count
- Off-by-one errors on interval ends
Trap Explanation:
PITFALL- Candidates often forget to add 1 to end event, causing wrong counts at interval ends.
Interviewer Note:
CONTEXT- Tests candidate's ability to trace line sweep event processing and off-by-one handling.
Master "Count of Intervals Containing Each Point" in Intervals
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Intervals Quizzes