首页 > 其他分享 >统计将重叠区间合并成组的方案数.18098728

统计将重叠区间合并成组的方案数.18098728

时间:2024-03-27 12:55:53浏览次数:30  
标签:right 重叠 18098728 ran ranges int 组中 成组 区间

统计将重叠区间合并成组的方案数

给你一个二维整数数组 ranges ,其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间(包括二者)的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成 两个 组(可以为空),满足:

每个区间只属于一个组。
两个有 交集 的区间必须在 同一个 组内。
如果两个区间有至少 一个 公共整数,那么这两个区间是 有交集 的。

比方说,区间 [1, 3] 和 [2, 5] 有交集,因为 2 和 3 在两个区间中都被包含。
请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大,将它对 109 + 7 取余 后返回。

 

示例 1:

输入:ranges = [[6,10],[5,15]]
输出:2
解释:
两个区间有交集,所以它们必须在同一个组内。
所以有两种方案:
- 将两个区间都放在第 1 个组中。
- 将两个区间都放在第 2 个组中。
示例 2:

输入:ranges = [[1,3],[10,20],[2,5],[4,8]]
输出:4
解释:
区间 [1,3] 和 [2,5] 有交集,所以它们必须在同一个组中。
同理,区间 [2,5] 和 [4,8] 也有交集,所以它们也必须在同一个组中。
所以总共有 4 种分组方案:
- 所有区间都在第 1 组。
- 所有区间都在第 2 组。
- 区间 [1,3] ,[2,5] 和 [4,8] 在第 1 个组中,[10,20] 在第 2 个组中。
- 区间 [1,3] ,[2,5] 和 [4,8] 在第 2 个组中,[10,20] 在第 1 个组中。

思路: 合并区间,统计组数,计算子集.

方法一: (26/32 TEL) 结构体加循环遍历已合并区间
用结构体数组去存储当前的组,并将新区间不断合并。

class Solution {
public:
    struct data{
        int left;
        int right;
    }ran[100010];

    static bool cmp(vector<int>a,vector<int>b){
        return a[0]<b[0];
    }

    int countWays(vector<vector<int>>& ranges) {
        sort(ranges.begin(),ranges.end(),cmp);
        int ran_len=0;
        for(int i=0;i<ranges.size();i++){
            int left=ranges[i][0];
            int right=ranges[i][1];
            int flag=0;
            //匹配是否有相交区间,并合并区间
            for(int j=0;j<ran_len;j++){
                if(left>=ran[j].left&&left<=ran[j].right){
                    if(right>ran[j].right)  ran[j].right=right;
                    flag=1;
                }
                if(right>=ran[j].left&&right<=ran[j].right){
                    if(left<ran[j].left)    ran[j].left=left;
                    flag=1;
                }
                if(left<ran[j].left&&right>ran[j].right){
                    ran[j].left=left;
                    ran[j].right=right;
                    flag=1;
                }
                if(flag)
                    break;
            }
            if(!flag){
                ran[ran_len].left=left;
                ran[ran_len].right=right;
                ran_len++;
            }
        }

        for(int i=0;i<ran_len;i++){
            cout<<ran[i].left<<" "<<ran[i].right<<endl;
        }

        int res=1;
        for(int i=0;i<ran_len;i++){
            res=((res%1000000007)*2)%1000000007;
        }
        return res;
    }
};

区间合并部分时间复杂度O(n*len())

方法二 固定左端点,合并

class Solution {
public:
    struct data{
        int left;
        int right;
    }ran[100010];

    static bool cmp(vector<int>a,vector<int>b){
        return a[0]<b[0];
    }

    int countWays(vector<vector<int>>& ranges) {
        sort(ranges.begin(),ranges.end(),cmp);
        int res=1;
        for(int i=0;i<ranges.size();){
            int right=ranges[i][1];
            int j=i+1;
            //区间相交
            while(j<ranges.size()&&ranges[j][0]<=right){
                //更新右侧区间
                right=max(right,ranges[j][1]);
                j++;
            }
            //一组结束
            res=res*2%1000000007;
            i=j;
        }
        return res;
    }
};

时间复杂度:
O(nlogn) sort + O(n)区间合并 = O(nlogn)

标签:right,重叠,18098728,ran,ranges,int,组中,成组,区间
From: https://www.cnblogs.com/SkyDusty/p/18098738

相关文章

  • 【工程应用九】再谈基于离散夹角余弦相似度指标的形状匹配优化(十六角度量化+指令集加
    继去年上半年一鼓作气研究了几种不同的模版匹配算法后,这个方面的工作基本停滞了有七八个月没有去碰了,因为感觉已经遇到了瓶颈,无论是速度还是效率方面,以当时的理解感觉都到了顶了。年初,公司业务惨淡,也无心向佛,总要找点事情做一做,充实下自己,这里选择了前期一直想继续研究的基于......
  • Qt 布局中控件重叠、挤压的解决方法
    问题描述:在QtDesigner中设计布局时,对所有控件使用QGridLayout、QHBoxLayout或QVBoxLayout布局设置。可以正常预览(Preview),但C++编译后,所有控件挤到一起,布局设置失效。问题解析:预览时正常,说明不是Qt的问题,应该与C++代码有关。问题解决:查看与ui关联的代码,发现这个......
  • 435. 无重叠区间c
    typedefstructnode{intleft;intright;}bounds;intcmp(constvoid*a,constvoid*b){bounds*x=(bounds*)a;bounds*y=(bounds*)b;if(x->right>y->right)return1;return-1;}interaseOverlapIntervals(int**interva......
  • (36/60)无重叠区间、划分字母区间、合并区间
    无重叠区间leetcode:435.无重叠区间贪心法思路去掉最少的区间数就是最少重叠区间对的个数。(成对的算,因为一对里面需要去掉一个)类似射气球的处理方式。左边界法:按左边界从小到大排序。遍历每个元素。取当前元素右边界为right判断是否重叠。如果[i]right>[i+1]left......
  • 代码随想录算法训练营第三十六天 | 56. 合并区间,763.划分字母区间,435. 无重叠区间
    435.无重叠区间 已解答中等 相关标签相关企业 给定一个区间的集合 intervals ,其中 intervals[i]=[starti,endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。 示例1:输入:intervals=[[1,2],[2,3],[3,4],[1,3]]输出:1解......
  • 代码随想录算法训练营第三十六天| ● 435. 无重叠区间 ● 763.划分字母区间 ● 56.
    无重叠区间 题目链接:435.无重叠区间-力扣(LeetCode)思路:我的思路是先将所有区间按左端点从小到大排序,左端点相同时右端点从小到大排序。接下来遍历数组,如果下一个区间与该区间有重叠部分,count加1,同时遍历下下一个区间(下一个区间被视为删除),同时如果下一个区间被包含在该区间中,......
  • 代码随想录 day36 无重叠区间 划分字母区间 合并区间
    无重叠区间这里的思路是找到有几个非重叠区间然后总数减去非重叠区间就是剩下的重叠区间数首先排好序按左或者右都可以这里按左排好然后发现边界不重叠就++边界重叠那么由于左边界优先对齐了所以右边界更新作为一个新的整体区间和下一个区间比较划分字母区间......
  • css中的resize设置、高度没有对齐、表单在校验、边框发生重叠
    小知识点汇总css❓:css中的resize设置......
  • 【LeetCode 2494. 合并在同一个大厅重叠的活动】[MySQL 用户变量/Pandas]面向过程编程
    目录题目地址MySQL代码等效pandas代码题目地址https://leetcode.cn/problems/merge-overlapping-events-in-the-same-hall/MySQL代码#WriteyourMySQLquerystatementbelowwitht2as(select*#----只需要改动这里的逻辑,其他不要动。注意里面的语句是“顺序......
  • 算法学习Day36重叠区间
    Day36重叠区间ByHQWQF2024/01/21笔记435.无重叠区间给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间[1,2]和[2,3]的边界相互“接触”,但没有相互重叠。示例1:输入:[[1,2],[2,3],[3,4],[1......