What is the time and space complexity of Non-Overlapping Intervals?

Time complexity: O(n log n). Space complexity: O(1).

Non-Overlapping Intervals

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Non-Overlapping Intervals

Approach

Sort intervals by END time (this is the key greedy insight). Keep the first interval. For each subsequent interval, if it starts before the previous end, it overlaps and must be removed. Otherwise, keep it and update the end boundary.

Complexity Analysis

Time: O(n log n)
Space: O(1)

Pattern

Sort + Greedy

Why It Works

Sorting by end time and always keeping the interval that ends earliest leaves maximum room for future intervals. This greedy choice is optimal because an interval with an earlier end time can never be worse than one with a later end time — it blocks fewer future intervals.

Updated Feb 2026