Why Intervals Are a Common Problem Pattern in DSA Python - Performance Analysis

Time Complexity: Why Intervals Are a Common Problem Pattern

O(n log n)

Understanding Time Complexity

Intervals problems often involve checking or merging overlapping ranges. Understanding their time complexity helps us know how fast these operations run as input grows.

We want to find out how the number of intervals affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Merge overlapping intervals
intervals = [[1,3],[2,6],[8,10],[15,18]]
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
    if not merged or merged[-1][1] < interval[0]:
        merged.append(interval)
    else:
        merged[-1][1] = max(merged[-1][1], interval[1])

This code sorts intervals and merges any that overlap into one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the list of intervals and then looping through each interval once.
• How many times: Sorting takes time based on all intervals (n), and the loop runs once for each interval (n times).

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	About 10 log 10 + 10 = 40 operations
100	About 100 log 100 + 100 = 700 operations
1000	About 1000 log 1000 + 1000 = 10,000 operations

Pattern observation: The work grows a bit faster than the number of intervals because of sorting, but the merging loop grows linearly.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to merge intervals grows a little faster than the number of intervals because sorting takes extra steps.

Common Mistake

[X] Wrong: "Merging intervals is just O(n) because we only loop once."

[OK] Correct: Sorting the intervals first takes extra time, which dominates the total work, so the overall time is more than just one loop.

Interview Connect

Knowing why intervals problems often need sorting and merging helps you explain your approach clearly and shows you understand how input size affects performance.

Self-Check

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