贪心算法解决区间问题：合并、选点、覆盖、最大不相交

一、前言区间问题是贪心算法中的高频考点而贪心算法是解决这类问题的 “黄金搭档”。本文将系统讲解基于贪心算法的四类经典区间问题区间合并、区间选点、区间覆盖、最大不相交区间数量帮助你彻底掌握这类问题的解题思路。二、核心思想贪心算法的本质贪心算法的核心是每一步都做出局部最优的选择从而希望最终得到全局最优解。对于区间问题贪心策略的关键在于对区间进行合理排序(通常按照左端点右端点排序)每一步选择当前最优的区间三、经典区间问题详解3.1 区间合并问题描述给定n个区间集合intervalsn[l,r],请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。例如输入:intervals{[1,2],[1,3],[2,3],[3,4],[6,8]}输出{[1,4],[6,8]}解题思路如果我们讲输出的数组作为res,那么res一开始为空我们选择讲区间的左端点升序排序。遍历加入res中这样res的最右端点(res最后一个区间的右端点maxR)作为判断依据如果要加入的区间的左端点l大于maxR,那么他与res的所有区间不重叠res将其加入否则存在重叠maxRmax(maxR,区间的右端点).算法模板vectorvectorint merge(vectorvectorint intervals) { int nintervals.size(); if(intervals.size()0)return {}; sort(intervals.begin(),intervals.end()); vectorvectorint merged; for(int i0;in;i){ int Lintervals[i][0];int Rintervals[i][1]; if(!merged.empty()Lmerged.back()[1]){ merged.back()[1]max(merged.back()[1],R); } else{ merged.emplace_back(vectorint({L,R})); } } return merged; }实战56. 合并区间 - 力扣LeetCode57. 插入区间 - 力扣LeetCode3.2区间选点问题描述给定若干区间选择最少的点使得每个区间至少包含一个点。例如 intervals{[1,2,2],[2,4,2],[1,4,3]}[l,r,num],,[l,r]是区间num是要求从区间选择的数字数量解题思路将区间右端点排序选第一个区间的右端点作为第一个点从右往前选数字这样能保证后面排序的区间内已经覆盖的点数最多可以抽象的理解区间A为了让后面区间B少选些点,尽量可能在区间B可能会覆盖的区间(就是从A区间从右往左)选择点后续区间遍历比如区间A[2,7,2]里7,6,被选择了B[4,8,4],由于7,6,已经选择选择4和8代码模板int minPoints(vectorvectorint intervals) { // 按右端点排序 sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b) { return a[1] b[1]; }); // 找到最右端的坐标方便标记点 int maxR 0; for (auto interval : intervals) { maxR max(maxR, interval[1]); } vectorbool used(maxR 1, false); // 标记某个点是否已被选 int totalPoints 0; for (auto interval : intervals) { int l interval[0]; int r interval[1]; int need interval[2]; // 统计区间内已选的点数 int cnt 0; for (int pos l; pos r; pos) { if (used[pos]) cnt; } // 如果还不够从右往左补点 if (cnt need) { int left need - cnt; for (int pos r; pos l left 0; pos--) { if (!used[pos]) { used[pos] true; cnt; left--; totalPoints; } } } } return totalPoints; }实战P1250 种树 - 洛谷P1325 雷达安装 - 洛谷3.3 区间覆盖问题描述一个目标区间[0, target]和n个候选区间要求选择最少的候选区间使其完全覆盖目标区间。例如 [0,20]是目标区间候选区间有[0,10],[5,15],[10,20]解题思路候选区间左端点排序维护一个已经选择的右端点maxR,在所有满足候选区间的左边界maxR里选择右端点最大的更新maxR,直到覆盖目标区间int minCover(vectorvectorint intervals, int target) { // 1. 按左端点排序 sort(intervals.begin(), intervals.end()); int res 0; int curEnd 0; // 当前已覆盖到的最右位置 int i 0; int n intervals.size(); while (curEnd target) { int maxNext curEnd; // 在能选的区间中能达到的最远右端点 // 2. 在所有左端点 curEnd 的区间中选右端点最大的 while (i n intervals[i][0] curEnd) { maxNext max(maxNext, intervals[i][1]); i; } // 3. 如果无法延伸说明覆盖失败 if (maxNext curEnd) { return -1; } // 4. 使用这个区间更新覆盖范围 curEnd maxNext; res; } return res; }实战1326. 灌溉花园的最少水龙头数目 - 力扣LeetCode3.4最大不相交区间问题描述给定若干区间选择最多数量的区间使得这些区间互不相交。例如{[1,3],[1,2],[2,3],[3,4]}中选择{[1,2],[2,3],[3,4]}解题思路与区间选点思路一样按区间右端点升序排序选第一个区间然后依次选择与已选区间不相交的区间代码模板int eraseOverlapIntervals(vectorvectorint intervals) { if (intervals.empty()) return 0; // 按右端点排序 sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b) { return a[1] b[1]; }); int count 1; // 至少可以选第一个区间 int lastEnd intervals[0][1]; for (int i 1; i intervals.size(); i) { // 如果当前区间左端点 上一个选中区间的右端点说明不重叠 if (intervals[i][0] lastEnd) { count; lastEnd intervals[i][1]; } // 否则重叠跳过当前区间即移除它 } // 返回需要移除的区间数量 总数 - 最多保留数 return intervals.size() - count; }实战435. 无重叠区间 - 力扣LeetCode