首页 > 其他分享 >贪心:重叠区间问题

贪心:重叠区间问题

时间:2024-05-09 18:04:03浏览次数:22  
标签:边界 重合 当前 区间 贪心 重叠

leetcode452,435

假设有intervals[][]这么一个二维数组,我们要找到其中的重叠区间个数:

  解题思路:分两种情况讨论即可:

    首先我们需要对区间进行一个排序,为了尽量让相邻的区间重叠,以便后续操作

    1.如果当前区间的左边界和上个区间的右边界不重合,那么这两个区间肯定是不重合的

    2.如果当前区间的左边界和上个区间的右边界重合,那么最好的情况下,只有这两个区间是重合的

      如果只是简单的判断有多少个重叠区间:我们只需本区间和前一个区间比对即可

      如果是求删除最小区间保证无重叠区间:如何判断第三个,乃至更多的区间与他们重合呢?这里我们就需要修改区间的边界值,已知两个区间重合之后,我们让当前区间的右边界取当前区间与前一个区间右边界的最小值。然后再回到上述循环中,最终我们就可以求出重叠区间。如下图

      

 

标签:边界,重合,当前,区间,贪心,重叠
From: https://www.cnblogs.com/kun1790051360/p/18182830

相关文章

  • leedcode-分发饼干(贪心算法)
    自己写的,没有使用排序,会超出时间限制:classSolution:deffindContentChildren(self,g:List[int],s:List[int])->int:iflen(s)==0:return0count=0foriinrange(len(g)):mydict={}forjin......
  • 一些贪心的解题报告
    一些贪心的解题报告贪心题一般来说都是观察结论远简单于严谨证明,所以不会过多的去证明。1.Treecompass题目来源codeforcesdiv1934Chttps://codeforces.com/problemset/problem/1943/C题面翻译给定一棵节点数为\(n\)的树(\(1\len\le2\cdot10^3\)),一开始节点都是白色......
  • 蓝桥杯-k倍区间
    给定一个长度为N的数列,A1,A2,…AN,如果其中一段连续的子序列Ai,Ai+1,…Aj之和是K的倍数,我们就称这个区间[i,j]是K倍区间。你能求出数列中总共有多少个K倍区间吗?输入格式第一行包含两个整数N和K。以下N行每行包含一个整数Ai。输出格式输出一个整数,代表K倍......
  • php合并时间区间
    需要写一段合并时间区间的代码,写个demo记录下<?php$arr=[["2024-04-1611:25:46","2024-04-1612:19:21"],["2024-04-1603:14:06","2024-04-1610:13:21"],["2024-04-1613:14:59","2024-04-1615:44:46"],......
  • 异或与区间加题解
    异或与区间加题解简要题意给定\(n,m,K,a_{1...n}\),和\(m\)个三元组\((x_i,y_i,z_i)\),定义\(calc(l,r)=a_l\bigoplusa_{l+1}\bigoplus...\bigoplusa_r\)。对于每个三元组\((x,y,z)\),对所有满足\(x\lel\ler\ley\,\calc(l,r)=K\)的区间\((l,r)\)内的每个数\(b......
  • 说说你对贪心算法、回溯算法的理解?应用场景?
    一、贪心算法贪心算法,又称贪婪算法,是算法设计中的一种思想其期待每一个阶段都是局部最优的选择,从而达到全局最优,但是结果并不一定是最优的举个零钱兑换的例子,如果你有1元、2元、5元的钱币数张,用于兑换一定的金额,但是要求兑换的钱币张数最少如果现在你要兑换11元,按照贪心算法......
  • 算法学习笔记(14):区间最值操作和历史最值问题
    区间最值操作,历史最值问题来源吉老师2016集训队论文,oiwiki,网络上各种博客。概述区间最值操作指的是:将所有的$i\in$\((l,r)\),\(a_i=min或max(a_i,k)\)。历史最值问题指的是:新定义一个数组\(b[]\),\(b[i]=max或min(b[i],a[i])\)。还有一种是历史版本和,即\(......
  • 力扣-598. 区间加法 II
    1.题目题目地址(598.区间加法II-力扣(LeetCode))https://leetcode.cn/problems/range-addition-ii/题目描述给你一个mx n的矩阵 M和一个操作数组op。矩阵初始化时所有的单元格都为0。ops[i]=[ai,bi]意味着当所有的0<=x<ai和0<=y<bi时,M[x][y]应......
  • 36天【代码随想录算法训练营34期】第八章 贪心算法 part05( ● 435. 无重叠区间 ● 7
    435.无重叠区间classSolution:deferaseOverlapIntervals(self,intervals:List[List[int]])->int:count=0intervals.sort(key=lambdax:x[0])foriinrange(1,len(intervals)):ifintervals[i][0]<intervals[i-......
  • 56. 合并区间(leetcode)
    https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked合并区间练习题typedefpair<int,int>PII;vector<PII>segs;classSolution{public:vector<vector<int>>merge(vector<vector<int>>......