首页 > 其他分享 >力扣 435. 无重叠区间

力扣 435. 无重叠区间

时间:2023-04-23 13:11:42浏览次数:46  
标签:prev 重叠 删除 力扣 intervals 移除 区间 435

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 <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

题解

为了方便比对,首先会排序。接下来考虑,当重叠却不包含时,如[1,5],[3,6],应该优先删除哪个呢?

实际上,排序后,下一个元素[start>=3,end]假设为[6,7]

  • 如果删除[1,5],则[3,6][6,7]仍然是重叠的,还需要再删除一个;
  • 如果删除[3,6][1,5][6,7]不再重叠,可以消耗更少的删除次数。

当然下一个元素不一定刚好就是与[1,5]不重叠的,只是说,优先删除[3,6],会利于减少后面出现的重叠情况。

另一种情况重叠并且包含,如[1,10],[2,3][2,3]包含在[1,10]中,根据之前的理解,为了减少后面出现的重叠情况,应该优先删除较长的元素[1,10],这样如果后面出现[4,5],将不会与[2,3]重叠。

那么在编码中,使用变量prev记录上一个未删除元素的下标,接下来通过当前下标cur遍历元素:

  • 如果出现重叠,intervals[cur][0]<intervals[prev][1],则需要删除一个元素,cnt++,接下来需要判断是哪种重叠情况:
    • 重叠却不包含,如[1,3] [2,5],优先移除[2,5],则prev不变,仍然指向[1,3]
    • 重叠并且包含,如[1,5] [2,3]优先移除[1,5]prev右移动,指向[2,3]
  • 不重叠,如[1,3] [4,5]cnt不需要累计,直接右移动prev即可;
查看代码
 class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int cnt=0;
        int prev=0;
        sort(intervals.begin(),intervals.end());
        for(int cur=1;cur<intervals.size();++cur){
            //有重叠
            if(intervals[cur][0]<intervals[prev][1]){
                ++cnt;//重叠移除一个
                //[1,3] [2,5] 优先移除[2,5],则prev不变,而[1,5] [2,3]优先移除[1,5],prev右移动
                if(intervals[cur][1]<=intervals[prev][1]){
                    prev=cur;
                }
            }
            else{//[1,3] [4,5]不重叠,移动prev即可
                prev=cur;
            }
        }
        return cnt;
    }
};

 

标签:prev,重叠,删除,力扣,intervals,移除,区间,435
From: https://www.cnblogs.com/fudanxi/p/17346255.html

相关文章

  • 力扣844(Java)-比较含退格的字符串(简单)
    题目:给定s和t两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回true。#代表退格字符。注意:如果对空文本输入退格字符,文本继续为空。 示例1:输入:s="ab#c",t="ad#c"输出:true解释:s和t都会变成"ac"。示例2:输入:s="ab##",t="c#d#"输出:true......
  • 【力扣-TS解题】1、回文数
    给你一个整数x,如果x是一个回文整数,返回true;否则,返回false。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121是回文,而123不是来源:力扣(LeetCode)转为字符串把数字转为字符串反转整个字符串对比两个字符串functionisPalindrome(x:number):b......
  • 力扣---238. 除自身以外数组的乘积
    给你一个整数数组 nums,返回数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32位整数范围内。请不要使用除法,且在 O(n)时间复杂度内完成此题。 示例1:输......
  • 力扣——554砖墙(c语言)
    title:力扣——554砖墙(c语言)题目描述:你的面前有一堵矩形的、由多行砖块组成的砖墙。这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。砖墙由行的列表表示。每一行都是一个代表从左至右每块砖的宽度的整数列表。如果你画的线只是从砖块的边......
  • 力扣——6.动态规划
    title:动态规划6、最长上升子序列(1)采用动态规划,算法复杂度为O(n*n)intlengthOfLIS(int*nums,intnumsSize){inti,j,max=1;if(NULL==nums||0==numsSize){return0;}int*dp=(int*)malloc(numsSize*sizeof(int));memset(dp,0,nu......
  • 力扣——21.合并两个有序链表(c语言)
    title:力扣——21.合并两个有序链表(c语言)将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4,1->3->4输出:1->1->2->3->4->41、递归实现:/***Definitionforsingly-linkedlist.*structListNode{......
  • 力扣——83.删除排序链表中的重复元素(c语言)
    title:力扣——83.删除排序链表中的重复元素(c语言)题目描述:给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。示例1:输入:1->1->2输出:1->2示例2:输入:1->1->2->3->3输出:1->2->3代码如下:/***Definitionforsingly-linkedlist.*structListNode{*......
  • 力扣——121.买卖股票的最佳时机(C语言)
    title:力扣——121.买卖股票的最佳时机(C语言)题目描述:给定一个数组,它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。注意:你不能在买入股票前卖出股票。示例1:输入:[7,1,5,3,6,......
  • 力扣——193.有效电话号码(shell)
    title:力扣——193.有效电话号码(shell)给定一个包含电话号码列表(一行一个电话号码)的文本文件file.txt,写一个bash脚本输出所有有效的电话号码。你可以假设一个有效的电话号码必须满足以下两种格式:(xxx)xxx-xxxx或xxx-xxx-xxxx。(x表示一个数字)你也可以假设每行前后没有......
  • 力扣——192.统计词频(shell)
    title:力扣——192.统计词频(shell)题目描述:写一个bash脚本以统计一个文本文件words.txt中每个单词出现的频率。为了简单起见,你可以假设:words.txt只包括小写字母和''。每个单词只由小写字母组成。单词间由一个或多个空格字符分隔。示例:假设words.txt内容如下:th......