LeetCode-435. Non-overlapping Intervals

LeetCode-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.

Example 1:

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

Example 2:

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

Example 3:

Input: [[1,2],[2,3]]Output: 0Explanation: You don't need to remove any of the intervals since they're already 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.

题解：

class Solution {public: static bool cmp(vector &a, vector &b) { if (a[0] != b[0]) { return a[0] < b[0]; } return a[1] < b[1]; } int eraseOverlapIntervals(vector>& intervals) { if (intervals.empty() == true) { return 0; } int n = intervals.size(); sort(intervals.begin(), intervals.end(), cmp); stack> s; s.push(intervals[0]); for (int i = 1; i < n; i++) { vector tmp = s.top(); if (intervals[i][0] >= tmp[1]) { s.push(intervals[i]); } else { s.pop(); tmp[0] = max(intervals[i][0], tmp[0]); tmp[1] = min(intervals[i][1], tmp[1]); s.push(tmp); } } return n - s.size(); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。