Non Overlapping Intervals Minimum Removal in DSA Python - Time & Space Complexity

Time Complexity: Non Overlapping Intervals Minimum Removal

O(n log n)

Understanding Time Complexity

We want to find out how fast the algorithm runs when removing intervals to avoid overlaps.

How does the time needed grow as the number of intervals increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = float('-inf')
    for interval in intervals:
        if interval[0] >= end:
            end = interval[1]
        else:
            count += 1
    return count
    

This code sorts intervals by their end time and counts how many intervals must be removed to avoid overlaps.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the intervals and then looping through them once.
• How many times: Sorting takes multiple comparisons depending on number of intervals; the loop runs once for each interval.

How Execution Grows With Input

Sorting takes more time as intervals increase, and the loop grows linearly.

Input Size (n)	Approx. Operations
10	About 30 to 40 operations
100	About 700 to 800 operations
1000	About 10,000 to 12,000 operations

Pattern observation: Sorting grows faster than looping, roughly n log n, while the loop grows linearly.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the number of intervals because of sorting, but the main loop adds only a simple pass.

Common Mistake

[X] Wrong: "The loop alone decides the time complexity, so it must be O(n)."

[OK] Correct: Sorting the intervals before looping takes more time, and it dominates the total time, making it O(n log n).

Interview Connect

Understanding how sorting affects time helps you explain your solution clearly and shows you know how to analyze real problems efficiently.

Self-Check

"What if the intervals were already sorted by end time? How would the time complexity change?"