Intervals - Remove Covered Intervals
What is the time complexity of the optimal solution that sorts intervals by start ascending and end descending, then scans once to count uncovered intervals?
What is the time complexity of the optimal solution that sorts intervals by start ascending and end descending, then scans once to count uncovered intervals?
medium🪤 Complexity Trap Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Analyze sorting step
Sorting n intervals by start and end costs O(n log n).Step 2: Analyze scanning step
Single pass scanning is O(n).Step 3: Combine complexities
Total time is dominated by sorting: O(n log n).Final Answer:
Option B -> Option BQuick Check:
Sorting dominates, scanning linear [OK]
Quick Trick: Sorting dominates time complexity [OK]
Common Mistakes:
MISTAKES- Assuming nested loops cause O(n^2)
- Confusing max width W as factor
Trap Explanation:
PITFALL- Candidates often mistake scanning as nested loops, inflating complexity.
Interviewer Note:
CONTEXT- Tests understanding of sorting and scanning complexity tradeoffs.
Master "Remove Covered Intervals" in Intervals
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Intervals Quizzes