Intervals - Minimum Interval to Include Each Query
Given the following code snippet implementing the min-heap approach, what is the output for intervals = [[1,4],[2,5],[7,10]] and queries = [3,6,8]?
Given the following code snippet implementing the min-heap approach, what is the output for intervals = [[1,4],[2,5],[7,10]] and queries = [3,6,8]?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Process query q=3
Intervals starting before or at 3 are [1,4] and [2,5]. Heap contains (4,4) and (4,5). Both cover 3. Minimum length is 4.Step 2: Process query q=6
No new intervals start before 6. Remove intervals ending before 6: both end at 4 and 5, so heap is empty. Result is -1.Step 3: Process query q=8
Interval [7,10] starts before 8, push (4,10). It covers 8. Result is 4.Final Answer:
Option C -> Option CQuick Check:
Heap correctly tracks active intervals and minimum length [OK]
Quick Trick: Check heap contents and removals at each query [OK]
Common Mistakes:
MISTAKES- Forgetting to remove expired intervals from heap
Trap Explanation:
PITFALL- Candidates often forget to pop intervals that ended before the query, causing wrong minimum length results.
Interviewer Note:
CONTEXT- Tests candidate's ability to trace heap-based interval coverage logic
Master "Minimum Interval to Include Each Query" in Intervals
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Intervals Quizzes