wordpress站点标题副标题换行,辽宁省朝阳市做网站,美妆网站建设方案,建网站算法题目
435. 无重叠区间
中等
相关标签
贪心 数组 动态规划 排序
给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠 。 示例 1:
输入: intervals [[1,2],[2,3],[3,4],[1,…题目
435. 无重叠区间
中等
相关标签
贪心 数组 动态规划 排序
给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。 示例 1:
输入: intervals [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后剩下的区间没有重叠。示例 2:
输入: intervals [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3:
输入: intervals [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间因为它们已经是无重叠的了。提示:
1 intervals.length 105intervals[i].length 2-5 * 104 starti endi 5 * 104
思路和解题方法 贪心算法的思维是选择右边界最小的区间以便给后续的区间留下更多的空间从而尽可能地避免重叠。首先我们将区间按照右边界进行排序这样可以保证在遍历过程中当前区间的左边界总是大于等于前一个区间的右边界。这样做的目的是为了确保我们尽量选择右边界较小的区间以便给后续的区间留下更多的空间。然后我们从第一个区间开始遍历。我们初始化一个计数器 count用于记录非交叉区间的个数初始值为 1因为至少有一个区间不会被移除。我们还维护一个变量 end用于记录当前区间的右边界。在遍历过程中对于每个区间我们检查它的左边界是否大于等于 end。如果是的话说明当前区间与前一个区间不重叠我们将 count 自增并更新 end 为当前区间的右边界。这样做的目的是选择一个新的非交叉区间。最后我们返回移除的区间个数即总区间个数减去非交叉区间的个数。这种贪心策略的思想是通过选择右边界最小的区间来最大化剩余区间的空间从而尽量避免重叠。虽然在每个步骤中我们只考虑了当前最优解但通过按照右边界排序我们可以确保得到的解是全局最优的。 复杂度 时间复杂度: O(n*logn) 时间复杂度为O(nlogn)其中n是区间的数量。主要耗时的操作是对区间进行排序时间复杂度为O(nlogn)。 遍历区间的过程需要线性时间时间复杂度为O(n)。 O(nlogn)O(n) O(nlogn) 空间复杂度 O(1) 空间复杂度为O(1)除了存储输入和输出以外代码没有使用额外的空间。 c 代码
class Solution {
public:// 按照区间右边界排序static bool cmp(const vectorint a, const vectorint b) {return a[1] b[1];}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0; // 如果区间为空则不需要移除任何区间sort(intervals.begin(), intervals.end(), cmp); // 按照区间右边界排序int count 1; // 记录非交叉区间的个数初始化为 1因为至少有一个区间不会被移除int end intervals[0][1]; // 记录当前区间的右边界for (int i 1; i intervals.size(); i) {if (end intervals[i][0]) {// 当前区间与前一个区间不重叠更新 count 和 endend intervals[i][1];count;}}// 移除的区间个数等于总区间个数减去非交叉区间的个数return intervals.size() - count;}
};思路二 左排序直接求答案
不同之处 首先这个代码中的 cmp 函数将区间按照左边界进行排序而不是右边界。这样做的目的是为了在遍历过程中更方便地判断重叠情况。具体来说我们可以用一个变量 end 来记录当前区间的右边界然后遍历每个区间如果当前区间的左边界大于等于 end说明当前区间与前一个区间不重叠我们更新 end 为当前区间的右边界否则说明当前区间与前一个区间重叠我们将 end 更新为两个区间右边界的最小值并将计数器 count 自增。 其次这个代码中的计数器 count 是从 0 开始的因为它记录的是重叠区间的个数而不是非交叉区间的个数。这个细节不影响算法的正确性只是需要注意计数器的初始值。 最后这个代码中的返回值是 count而不是 intervals.size() - count。这个细节也不影响算法的正确性只是需要注意返回值的含义。 class Solution {
public:static bool cmp(const vectorint a, const vectorint b) {return a[0] b[0]; // 按照左边界进行排序}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0;sort(intervals.begin(), intervals.end(), cmp); // 对区间按照左边界排序int count 0; // 记录重叠区间的个数int end intervals[0][1]; // 记录当前区间的右边界for (int i 1; i intervals.size(); i) {if (intervals[i][0] end) end intervals[i][1]; // 无重叠的情况更新右边界else { // 重叠情况end min(end, intervals[i][1]); // 更新右边界为两个区间右边界的最小值count; // 计数器自增记录重叠区间的个数}}return count; // 返回重叠区间的个数}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
