TIC
The Interns Company

Non-overlapping Intervals

MediumAcceptance: 46.8%
ArrayGreedySortingIntervals

Problem Statement

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Constraints:

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= starti < endi <= 5 * 10^4

Input Format:

  • An array of intervals, where each interval is represented as [start, end]

Output Format:

  • Return an integer representing the minimum number of intervals to remove.

Examples:

Example 1:

Input:

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

Output:

1

Explanation:

[1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input:

intervals = [[1,2],[1,2],[1,2]]

Output:

2

Explanation:

You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input:

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

Output:

0

Explanation:

You don't need to remove any of the intervals since they're already non-overlapping.

Solutions

Greedy Approach with Sorting by End Time

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

Sort intervals by end time and greedily select intervals that don't overlap. Count the intervals that need to be removed.

Alternative Approach - Sorting by Start Time

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

Sort intervals by start time and then choose to remove the interval that ends later when there's an overlap.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Sort intervals by end time: [[1,2],[2,3],[3,4],[1,3]] → [[1,2],[2,3],[3,4],[1,3]]
  2. Initialize prevEnd = 2 (end time of first interval)
  3. For interval [2,3]: start(2) >= prevEnd(2), no overlap, update prevEnd = 3
  4. For interval [3,4]: start(3) >= prevEnd(3), no overlap, update prevEnd = 4
  5. For interval [1,3]: start(1) < prevEnd(4), overlap detected, count = 1
  6. Return count = 1

Hints

Hint 1
Sorting the intervals can simplify the problem.
Hint 2
Consider sorting the intervals by their end times.
Hint 3
Once sorted by end times, use a greedy approach to keep intervals that end earliest.
Hint 4
When intervals overlap, always remove the one that ends later.

Video Tutorial

Non-overlapping Intervals - Greedy Approach

YouTube•Learn the Non-overlapping Intervals solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the intervals on a number line and see which intervals need to be removed to make the rest non-overlapping.

Key visualization elements:

  • current interval
  • previous end
  • intervals to remove

Similar Questions

Insert Interval

Medium

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.

Meeting Rooms

Easy

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings. In other words, check if there are any overlapping intervals.

Meeting Rooms II

Medium

Given an array of meeting time intervals where intervals[i] = [starti, endi], find the minimum number of conference rooms required to hold all meetings.

Merge Intervals

Medium

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Asked By

AmazonFacebookGoogleMicrosoftApple

Implementation Notes

This is a classic greedy algorithm problem using interval scheduling. The key insight is to sort intervals by their end times to optimize the number of non-overlapping intervals we can keep.