LeetCode435. Non-overlapping Intervals（贪心 / 动态规划）

Medium
Accepted：36,286
Submissions：87,349

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:

You may assume the interval's end point is always bigger than its start point.
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.

链接

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

题意

给定一些区间的集合，问你要删除的最少区间的数量使得剩余的区间不重叠。保证区间的结束点大于起始点以及边界值相同不算重叠。

题解

求删除的最少区间数量可以转化为求集合中不重叠的区间最多有多少个。

为了方便判断重叠，我们可以对区间进行排序。按照起始点从小到大排序，起始点相同时按终止点从小到大排序。

这样我们就将问题转变成了类“最长上升子序列”，区间化点，对于当前区间，如果它的左端点大于等于前面的右端点那么就加1。

此外，还可以使用“贪心”来做，同样先对区间进行排序，但是按照终止点从小到大排序，每次选择终止点最小的，这样就可以给后面的区间留出更多的空间，从而选择更多不重叠的空间。

贪心时间复杂度：$O(n)$，动态规划时间复杂度：$O(n^2)$。

代码

Runtime: 12 ms, faster than 86.40% of C++ online submissions for Non-overlapping Intervals.
Memory Usage: 9.8 MB, less than 73.08% of C++ online submissions for Non-overlapping Intervals.

bool cmp(const Interval & a, const Interval & b)
{
    if (a.end != b.end)
        return a.end < b.end;
    return a.start < b.start;
}

class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {
        int n = intervals.size();
        if (n == 0)
            return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int pre = 0, ans = 1;
        for (int i = 1; i < n; ++i)
        {
            if (intervals[i].start >= intervals[pre].end)
            {
                ++ans;
                pre = i;
            }
        }
        return n - ans;
    }
};

Runtime: 396 ms, faster than 5.18% of C++ online submissions for Non-overlapping Intervals.
Memory Usage: 9.9 MB, less than 15.38% of C++ online submissions for Non-overlapping Intervals.

bool cmp(const Interval & a, const Interval & b)
{
    if (a.start != b.start)
        return a.start < b.start;
    return a.end < b.end;
}

class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {
        int n = intervals.size();
        if (n == 0)
            return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        vector <int> dp(n + 1, 1);
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (intervals[i].start >= intervals[j].end)
                    dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans = max(ans, dp[i]);
        return n - ans;
    }
};

The end.
2019年4月11日星期四