# 435. Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

1. You may assume the interval’s end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:

``````Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

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

Example 2:

``````Input: [ [1,2], [1,2], [1,2] ]

Output: 2

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

Example 3:

``````Input: [ [1,2], [2,3] ]

Output: 0

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

``````class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int res = 0, n = intervals.size(), last = 0;
sort(intervals.begin(), intervals.end());
for (int i = 1; i < n; ++i) {
if (intervals[i][0] < intervals[last][1]) {
++res;
if (intervals[i][1] < intervals[last][1]) last = i;
} else {
last = i;
}
}
return res;
}
};
``````

``````class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end());
int res = 0, n = intervals.size(), endLast = intervals[0][1];
for (int i = 1; i < n; ++i) {
int t = endLast > intervals[i][0] ? 1 : 0;
endLast = t == 1 ? min(endLast, intervals[i][1]) : intervals[i][1];
res += t;
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/435

Find Right Interval

Insert Interval

Merge Intervals

Maximum Length of Pair Chain

https://leetcode.com/problems/non-overlapping-intervals/

https://leetcode.com/problems/non-overlapping-intervals/discuss/91713/Java%3A-Least-is-Most

https://leetcode.com/problems/non-overlapping-intervals/discuss/91700/Concise-C%2B%2B-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation