Skip to main content
Talentd

Non-overlapping Intervals - Solution & Explanation

MediumArrayDynamic ProgrammingGreedySorting20 min readAsked at: Amazon, Microsoft, Apple +15
Practice this problem

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.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

 

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.

 

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

Approach Overview

Problem Overview: You are given a list of intervals where each interval has a start and end time. Some intervals overlap. The goal is to remove the minimum number of intervals so the remaining intervals do not overlap with each other.

Approach 1: Greedy by Earliest End Time (O(n log n) time, O(1) space)

The key observation: keeping the interval that finishes earliest leaves the most room for future intervals. Start by sorting intervals by their end time using sorting. Iterate through the intervals while tracking the end time of the last accepted interval. If the current interval starts before that end time, it overlaps and must be removed. Otherwise update the end pointer and keep it. This greedy decision works because choosing the earliest finishing interval always maximizes the number of non-overlapping intervals you can keep.

This approach relies on a classic interval scheduling strategy and only requires a single pass after sorting. The algorithm runs in O(n log n) time due to sorting and uses O(1) extra space (excluding input). Problems involving interval conflicts often combine array traversal with greedy decisions like this.

Approach 2: Dynamic Programming (O(n^2) time, O(n) space)

This method treats the problem similarly to finding the longest chain of compatible intervals. First sort intervals by start time. Define dp[i] as the maximum number of non-overlapping intervals that end with interval i. For each interval i, iterate over all previous intervals j. If intervals[j].end <= intervals[i].start, they do not overlap, so update dp[i] = max(dp[i], dp[j] + 1). After processing all intervals, the largest value in dp gives the maximum set of non-overlapping intervals.

The final answer equals total_intervals - max_non_overlapping. This solution is conceptually straightforward and highlights the relationship between interval scheduling and subsequence-style DP problems. However, the nested loop results in O(n^2) time and O(n) space.

Recommended for interviews: The greedy solution is the expected answer. Interviewers want to see if you recognize the interval scheduling pattern and apply sorting by end time. Mentioning the dynamic programming approach first can show deeper understanding, but implementing the O(n log n) greedy algorithm demonstrates strong algorithmic intuition.

Approach 1: Greedy Approach

The greedy approach involves sorting the intervals by their end times. Then, we iterate through the sorted list and count the number of overlapping intervals to remove. The idea is to always pick the interval with the earliest end time, which leaves more room for the remaining intervals.

Steps:

  1. Sort the intervals based on their end time.
  2. Initialize a variable to keep track of the end of the last added interval.
  3. Iterate through the sorted intervals and for each interval, check if it overlaps with the last added interval. If it does, increment the count of intervals to remove. If it doesn't, update the end time to the current interval's end time.

This C implementation sorts the intervals based on their end times using qsort. It then iterates through the sorted intervals, maintaining a count of the overlapping intervals to be removed and updating the end of the last included interval.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), excluding the input space for the intervals.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach utilizes dynamic programming to solve the problem. It is typically less efficient than the greedy method but serves as an illustrative illustration of tackling overlap problems using dp.

  1. Sort intervals based on start time to ensure a consistent order for dp evaluation.
  2. Define a dp array where dp[i] stores the maximum count of non-overlapping intervals up to i-th interval.
  3. Initialize each dp[i] to 1 as each interval can at least be alone considered non-overlapping.
  4. For each interval, check whether it can be included in the non-overlapping list built so far without causing overlap.
  5. The answer will be determined by the maximum value in the dp array.

This C solution sorts the intervals by start time and uses a dp array to store the longest non-overlapping subsequence up to each interval. It checks each interval against those before it to see if it can be appended without leading to overlap.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to nested loops for dp updates.
Space Complexity: O(n) required for the dp array.

Try this approach in the editor →

Approach 3: Sorting + Greedy

We first sort the intervals in ascending order by their right boundary. We use a variable pre to record the right boundary of the previous interval and a variable ans to record the number of intervals that need to be removed. Initially, ans = intervals.length.

Then we iterate through the intervals. For each interval:

  • If the left boundary of the current interval is greater than or equal to pre, it means that this interval does not need to be removed. We directly update pre to the right boundary of the current interval and decrement ans by one;
  • Otherwise, it means that this interval needs to be removed, and we do not need to update pre and ans.

Finally, we return ans.

The time complexity is O(n times log n), and the space complexity is O(log n), where n is the number of intervals.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), excluding the input space for the intervals.

Dynamic Programming Approach

Time Complexity: O(n^2) due to nested loops for dp updates.
Space Complexity: O(n) required for the dp array.

Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy (Sort by End Time)O(n log n)O(1)Best general solution. Optimal for interview settings and large inputs.
Dynamic ProgrammingO(n^2)O(n)Useful for understanding interval compatibility or when exploring DP formulations.

Video Solution

Non-Overlapping Intervals - Leetcode 435 - Python • NeetCode • 176,660 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Non-overlapping Intervals easy or hard?
Non-overlapping Intervals is rated Medium on LeetCode. The implementation is short, but the challenge is recognizing the greedy strategy of sorting by end time. Candidates who identify the interval scheduling pattern typically solve it quickly.
How to solve Non-overlapping Intervals in O(n)?
A strict O(n) solution is generally not possible because the intervals must be ordered first. The standard approach sorts intervals by end time, which costs O(n log n). If the intervals were already sorted by end time, the greedy scan itself would run in O(n).
What is the best approach for Non-overlapping Intervals?
The greedy approach that sorts intervals by end time is the optimal solution. After sorting, iterate through the intervals and keep track of the last selected end time. If an interval overlaps, remove it; otherwise keep it. This algorithm runs in O(n log n) time and O(1) extra space.
What data structure is used in Non-overlapping Intervals?
The solution mainly uses arrays to store intervals and sorting algorithms to order them by end time. The greedy approach only tracks the last chosen end value, while the dynamic programming approach uses an additional DP array to store optimal subproblem results.
What is the time complexity of Non-overlapping Intervals?
The optimal greedy solution runs in O(n log n) time due to sorting the intervals. After sorting, the algorithm scans the list once in O(n). The dynamic programming alternative takes O(n^2) time because it compares each interval with all previous ones.
Non-overlapping Intervals Python or Java solution approach?
In both Python and Java, the common solution sorts the interval list using a custom comparator based on the end value. Then iterate through the sorted intervals while tracking the last non-overlapping end. If the current start is smaller than the previous end, increment the removal count.
Is Non-overlapping Intervals asked at Google, Amazon, or Meta?
Interval scheduling and overlap removal problems appear frequently in interviews at companies like Google, Amazon, Meta, and Microsoft. The question tests understanding of greedy strategies, sorting, and recognizing optimal substructure in interval problems.

Ready to solve this problem?

Practice Non-overlapping Intervals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Determine if Two Events Have Conflict

Next

Minimum Number of Arrows to Burst Balloons