Bird
Raised Fist0

What is the time complexity of the optimal approach that inserts a new interval into a list of n intervals and merges overlapping intervals, where the approach is to append the new interval, sort all intervals by start time, then merge in one pass?

medium🪤 Complexity Trap Q13 of Q15
Intervals - Insert Interval
What is the time complexity of the optimal approach that inserts a new interval into a list of n intervals and merges overlapping intervals, where the approach is to append the new interval, sort all intervals by start time, then merge in one pass?
AO(n)
BO(n^2)
CO(n log n)
DO(log n)
Step-by-Step Solution
Solution:

  1. Step 1: Identify sorting cost

    Appending is O(1), but sorting n+1 intervals takes O(n log n) time.

  2. Step 2: Identify merging cost

    Merging intervals in one pass is O(n) since each interval is processed once.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Sorting dominates overall time complexity [OK]
Quick Trick: Sorting dominates time complexity -> O(n log n) [OK]
Common Mistakes:
MISTAKES
  • Assuming linear time because merging is O(n)
  • Confusing sorting cost with merging cost
  • Thinking recursion stack adds extra complexity
Trap Explanation:
PITFALL
  • Option A looks tempting because merging is O(n), but sorting is required and costs O(n log n).
Interviewer Note:
CONTEXT
  • Checks if candidate understands sorting cost dominates over linear merging.
Master "Insert Interval" in Intervals

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Intervals Quizzes
Count of Intervals Containing Each Point - Count of Intervals Containing Each Point - Quiz 2easy Count of Intervals Containing Each Point - Count of Intervals Containing Each Point - Quiz 4medium Data Stream as Disjoint Intervals - Data Stream as Disjoint Intervals - Quiz 14medium Interval List Intersections - Interval List Intersections - Quiz 11easy Meeting Rooms II (Minimum Conference Rooms) - Meeting Rooms II (Minimum Conference Rooms) - Quiz 2easy Merge Intervals - Merge Intervals - Quiz 6medium Minimum Interval to Include Each Query - Minimum Interval to Include Each Query - Quiz 4medium Non-overlapping Intervals (Max Non-Overlap) - Non-overlapping Intervals (Max Non-Overlap) - Quiz 11easy Non-overlapping Intervals (Max Non-Overlap) - Non-overlapping Intervals (Max Non-Overlap) - Quiz 7medium Remove Covered Intervals - Remove Covered Intervals - Quiz 4medium