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

Time Complexity: Non Overlapping Intervals Minimum Removal

O(n log n)

Understanding Time Complexity

We want to find 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.

// Sort intervals by end time
qsort(intervals, n, sizeof(Interval), compareEnd);

int count = 0;
int end = intervals[0].end;
for (int i = 1; i < n; i++) {
    if (intervals[i].start < end) {
        count++;
    } else {
        end = intervals[i].end;
    }
}
return count;
    

This code sorts intervals by their end time, then 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 array.
• How many times: Sorting compares elements multiple times, then a single loop runs through all intervals once.

How Execution Grows With Input

As the number of intervals grows, sorting takes more time, and the loop checks each interval once.

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: Operations grow faster than the input size but not as fast as its square; sorting dominates growth.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the number of intervals because sorting takes more work as input grows.

Common Mistake

[X] Wrong: "The loop checking overlaps is the slowest part, so complexity is O(n)."

[OK] Correct: Sorting the intervals takes more time than the single loop, so it controls the overall speed.

Interview Connect

Understanding this helps you explain how sorting affects performance and why greedy choices after sorting are efficient.

Self-Check

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