如何为一个网站做短连接,吉林市网站建设公司,山西营销网站建设那个公司好,建南沙做网站公司题意理解#xff1a; 给定一个区间的集合 intervals 要求需要移除区间#xff0c;使剩余区间互不重叠 目标#xff1a;最少需要移除几个区间。 解题思路#xff1a; 采用贪心思路解题#xff0c;什么是全局最优解#xff0c;什么是局部最优解。 全局最优解#xff0c;删… 题意理解 给定一个区间的集合 intervals 要求需要移除区间使剩余区间互不重叠 目标最少需要移除几个区间。 解题思路 采用贪心思路解题什么是全局最优解什么是局部最优解。 全局最优解删除最少的区间使剩下的区间不重叠。 局部最优尽可能识别重叠的区域并移除相应区间。 为了方便识别重叠区间我们以区间的左边界为准升序排列左区间一致以右区间升序排列。 最终的序列同起点的区间小区间总在最前面。 当第i个区间的左边界第i-1个区间的右边界时出现重叠区域需要删除的count; 当删除该区间后第i1个元素的左边界和最早截止的区间的右边界比较以保证更多的不重叠区间。 为了方便统一处理当记录删除一个区间时: 将要删除第i的区间右边界设为Math.min(第i-1区间的右边界,第i个区间的右边界) 1.贪心解题
我们使用count记录发生重叠要删除的区域。 public int eraseOverlapIntervals(int[][] intervals) {int count0;//对区间进行排序Arrays.sort(intervals,(o1,o2)-(o1[0] - o2[0]));//遍历区间,总是和最左边的区间比较for(int i1;iintervals.length;i){if(intervals[i][0]intervals[i-1][1]){//有重叠count;intervals[i][1]Math.min(intervals[i][1],intervals[i-1][1]);}//无重叠不操作}return count;}
2.分析 时间复杂度O(n logn) 排序所需时间O(nlogn)遍历的时间O(n) 空间复杂度O(logn) 排序所需的额外栈空间O(logn) n为输入数组的大小
