What is the time complexity of the optimal in-place merge intervals algorithm that first sorts the intervals and then merges them in one pass?

medium🪤 Complexity Trap Q13 of Q15

Intervals - Merge Intervals

AO(n log n) due to the sorting step dominating the runtime

BO(n) because merging is done in a single pass

CO(n²) because each interval is compared with all others during merging

DO(n log n) because merging requires binary searches for overlaps

Step-by-Step Solution

Step 1: Identify the sorting step complexity.
Sorting n intervals by start time takes O(n log n) time.
Step 2: Analyze the merging step complexity.
Merging intervals in one pass is O(n), which is dominated by sorting.
Final Answer:
Option A -> Option A
Quick Check:
Sorting dominates overall complexity, merging is linear. [OK]

Quick Trick: Sorting dominates, merging is linear [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often think merging compares all pairs, leading to O(n²), but merging is linear after sorting.

Interviewer Note:

CONTEXT

Checks if candidate understands sorting cost and linear merging step distinction.

Master "Merge Intervals" in Intervals

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Intervals Quizzes