Introduction

Non-overlapping Intervals is a classic interval scheduling problem.

You are given:

  • A collection of intervals

Goal:

Remove the minimum number of intervals so that the remaining intervals do not overlap.

Example

Input

 intervals = [[1,2],[2,3],[3,4],[1,3]]

Output

 1

Explanation

Remove [1,3]
Remaining intervals:
[1,2]
[2,3]
[3,4]
No overlap exists.

Key Observation

Keep the interval that finishes earliest.

An earlier ending interval leaves maximum space for future intervals.

Algorithm

  1. Sort intervals by ending time.
  2. Keep the first interval.
  3. Traverse remaining intervals.
  4. If overlap exists:
    • Remove current interval.
  5. Otherwise:
    • Keep interval.
    • Update ending time.
  6. Return total removals.

Dry Run

Input

 [[1,2],[2,3],[3,4],[1,3]]

Sort By End Time

 [[1,2],[2,3],[1,3],[3,4]]

Keep [1,2]

 end = 2

Check [2,3]

No overlapend = 3

Check [1,3]

 1 < 3Overlap Found
removals = 1

Check [3,4]

No overlapend = 4

Answer

 1

Approach : Greedy

Always keep the interval with the smallest ending time because it leaves maximum room for future intervals.

Practice

Complexity Analysis

Time Complexity: O(n log n)
Explanation: Sorting the intervals dominates the running time. The traversal itself takes O(n).

Space Complexity: O(1)
Explanation: Only a few extra variables are used apart from sorting.

Why This Problem is Important

This problem introduces interval scheduling, one of the most important greedy paradigms used in interviews and real-world scheduling systems.

Common Beginner Mistakes

  • Sorting by start time instead of end time.
  • Removing the wrong interval during overlap.
  • Updating end incorrectly.
  • Confusing it with Merge Intervals.

Interview Tip

Always mention:

Keeping the interval with the earliest ending time leaves the most space for future intervals and leads to the optimal solution.

Related Questions

  • Merge Intervals
  • Insert Interval
  • Meeting Rooms
  • Meeting Rooms II
  • Minimum Number of Arrows to Burst Balloons

Final Takeaway

Non-overlapping Intervals is a classic greedy interval scheduling problem. Sorting by ending time and always keeping the interval that finishes earliest guarantees the minimum number of removals.