MediumNo. 0435
Non-overlapping Intervals — LeetCode 435 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array, Dynamic Programming, Sorting
- On study lists
- Blind 75, NeetCode 150 and LeetCode 75
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
ans = len(intervals)
pre = -inf
for l, r in intervals:
if pre <= l:
ans -= 1
pre = r
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(log n)where n is the number of intervals
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 435. Non-overlapping Intervals is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0646 | Maximum Length of Pair Chain | Medium |
| 1262 | Greatest Sum Divisible by Three | Medium |
| 1363 | Largest Multiple of Three | Hard |
| 1402 | Reducing Dishes | Hard |
| 2708 | Maximum Strength of a Group | Medium |
| 0045 | Jump Game II | Medium |
Frequently asked questions
- How hard is LeetCode 435. Non-overlapping Intervals?
LeetCode 435. Non-overlapping Intervals is rated Medium on LeetCode.
- What is the time complexity of LeetCode 435. Non-overlapping Intervals?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 435. Non-overlapping Intervals?
The Python solution on this page uses O(log n), where n is the number of intervals auxiliary space.
- What topics does LeetCode 435. Non-overlapping Intervals cover?
LeetCode 435. Non-overlapping Intervals is tagged Greedy, Array, Dynamic Programming and Sorting on LeetCode.