问题转换为求最多的不重合区间的数量
超时的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](vector<int>& v1, vector<int>& v2)
{
return v1[0] < v2[0];
});
int n = intervals.size();
vector<int> dp(n, 1);
int ret = 1;
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(intervals[i][0] >= intervals[j][1])
{
dp[i] = max(dp[i], 1 + dp[j]);
ret = max(dp[i], ret);
}
}
}
return n - ret;
}
};
|
优化
参考300. 最长递增子序列的贪心+二分解法
顺便看看题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const auto& v1, const auto& v2)
{
return v1[1] < v2[1];
});
int right = intervals[0][1];
int ret = 1;
int n = intervals.size();
for(int i = 1; i < n; ++i)
{
if(intervals[i][0] >= right)
{
right = intervals[i][1];
++ret;
}
}
return n - ret;
}
};
|
如果右边那个可以的话，比右边那个右端点小的肯定也可以