0

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 Q13 of Q15

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?

AO(n log n) due to sorting plus O(n) scanning

BO(n log n) due to sorting, but scanning is O(n²) in worst case

CO(n) because scanning is linear and sorting is negligible

DO(n²) due to nested coverage checks

Step-by-Step Solution

Step 1: Identify sorting cost
Sorting n intervals by start and end takes O(n log n) time.
Step 2: Identify scanning cost
Single pass scanning to count uncovered intervals is O(n).
Final Answer:
Option A -> Option A
Quick Check:
Sorting dominates, scanning is linear [OK]

Quick Trick: Sorting dominates complexity, scanning is linear [OK]

Common Mistakes:

MISTAKES

Confuse scanning as nested loops O(n²)
Ignore sorting cost and say O(n)

Trap Explanation:

PITFALL

Some think scanning is nested or sorting is negligible, but sorting is O(n log n).

Interviewer Note:

CONTEXT

Tests understanding of sorting and scanning costs in interval problems.

Master "Remove Covered Intervals" in Intervals

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Intervals Quizzes