首页 > 其他分享 >力扣-设置交集大小至少为2

力扣-设置交集大小至少为2

时间:2023-07-29 11:01:05浏览次数:39  
标签:xi rs 交集 ins 力扣 int ls 设置 区间

1.问题描述

一个整数区间 [a, b]  ( a < b ) 代表着从 a 到 b 的所有连续整数,包括 a 和 b。

给你一组整数区间intervals,请找到一个最小的集合 S,使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。

输出这个最小集合S的大小。

示例 1:

输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]

输出: 3

解释:

考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。

且这是S最小的情况,故我们输出3。

示例 2:

输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]

输出: 5

解释:

最小的集合S = {1, 2, 3, 4, 5}.

2.输入说明

首先输入intervals 的区间个数m(范围为[1, 3000]),

然后输入m行,每行2个数字( [0, 10^8]范围内的整数),表示区间的左、右边界。

3.输出说明

输出一个整数。

4.范例

输入:

4
1 2
2 3
2 4
4 5

输出:

5

5.思路

(1)根据题设要求,S可以不是连续段

(2)对intervals(后面简称ins)进行排序,按左区间从小到大排序,当左区间一样时,按右区间从大到小排序,其原因:假设我们有一个ins = [[2,3],[3,4],[5,10],[5,8]] (已排好序), 只要我们满足了和[5,8]的交集大于等于2,则对于[5,10](左区间相同,右区间降序,保证在左区间相同的情况下让区间范围最小的在最右边)这个区间来说,必定是满足交集大于等于2的,因为小区间满足,大区间必然满足,反过来不一定。

(3)在左区间相同的情况下,我们取最小区间的两个元素就可以满足所有左区间相同的区间。因此我们贪心的取interval[n-1][0]和interval[n-1][0] + 1做为开始的两个集合元素,设初始两个元素为ls和rs,则 ls = ins[n - 1][0],rs = ins[n - 1][0] + 1。

设选取的两个数分别为ls 和rs,此时的答案为2,接下来我们遍历后续的所有区间,对于当前区间的起点xi和终点yi,根据排序有 xi<= ls ,有以下几种情况:

若yi >= rs,则是一个大区间,一定满足交集为2的情况;
若yi < ls,则一定没有交集,此需要将当前区间最小的两个数 xi 以及xi + 1加入到S中,同时更新 ls 为 xi + 1,rs 为 xi , 即贪心的取ls = xi, rs = xi + 1
若ls <= yi < rs,则有一个交集,此需要保留和区间[xi , yi]的交点,即使 ls ,另一个取能囊括区间更多点的点,即 xi ,将这两个点加入到S中,并更新 ls 和 rs ,即贪心的取 rs  = ls,ls= xi
保证每次都是取左边界或者左边界和左边界+1

6.代码

//C++
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const vector<int> &a,const vector<int> &b)
{
    if(a[0]==b[0])//若左端一样,按照右边大到小排序
    {
        return a[1]>b[1];
    }
    return a[0]<b[0];
}
class Solution
{
public:
    int intersectionSizeTwo(vector<vector<int> > &ins)
    {
        //1.排序--左边升序,若左边相同,右边降序
        sort(ins.begin(), ins.end(),cmp);
        //2.从后往前遍历
        //取ins[n-1][0]和ins[n-1][0]+1作为开始的两个集合元素
        int res = 2, ls = ins.back()[0], rs = ls + 1;
        for(int i = ins.size() - 2; i >= 0; i--){
            if(ins[i][1] >= rs){  // 有两个及以上的交点
                continue;
            }else if(ins[i][1] < ls){  // 没有交点
                ls = ins[i][0];
                rs = ins[i][0] + 1;
                res += 2;
            }else{  // 一个交点
                rs = ls;
                ls = ins[i][0];
                res++;
            }
        }
        return res;
    }
};
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    Solution solve;
    int m;
    cin>>m;
    int data;
    vector<vector<int> >ins;
    for(int i=0;i<m;i++)
    {
        vector<int> row;
        for(int j=0;j<2;j++)
        {
            cin>>data;
            row.push_back(data);
        }
        ins.push_back(row);
    }
    int res=solve.intersectionSizeTwo(ins);
    cout<<res<<endl;
    return 0;
}

 

标签:xi,rs,交集,ins,力扣,int,ls,设置,区间
From: https://www.cnblogs.com/ohye/p/17589452.html

相关文章

  • odoo设置字段字体颜色的样式的方法decoration
    源码设置如下图:decoration-it="product_uom_qty1andprice_unit40"decoration-danger="product_uom_qty==1"效果如下图:基本样式列表:'decoration-bf',#字体加粗'decoration-it',#字体倾斜'decoration-danger',......
  • 什么是FL Studio水果音乐制作软件,fl studio怎么设置中文语言切换详细操作
    如今,越来越多的音乐人选择使用音乐制作软件来进行音乐的创作,一台电脑、一款软件以及一个外接MIDI就是一个小型的音乐工作站。FLStudio成了音乐界萌新的首选,目前最新的版本为FLStudio21.0.3.3517版本。FLStudio21.0.3.35171是一款功能十分强大的音乐制作软件,可以让你的电脑变成小......
  • 安装spark local运行出现错误NoClassDefFoundError: org/slf4j/Logger 原来是要设置
    Error:Unabletoinitializemainclassorg.apache.spark.deploy.SparkSubmitCausedby:java.lang.NoClassDefFoundError:org/slf4j/Logger HowtoinstallsparklocallyConsideringsparkwithouthadoopbuilt-in.Downloadhadoopunpackto/opt/hadoop/Downloadsp......
  • FPGA vivado quartus 设置外挂 编辑器
     1.vivado   tools->settings->editor ->customeditor... C:\\pg\\MicrosoftVSCodeInsiders\\Code-Insiders.exe[filename]  2.quartus tools->options->preferredtexteditortexteditor:custom command-line:"C:\pg\M......
  • Git常用命令(Git全局设置、获取Git仓库)
         ......
  • nvidia显卡设置 让显卡发挥最大的性能
    1、打开官网https://www.nvidia.cn/geforce/drivers/查看电脑系统位数和显卡(GPU)的版本产品系列:Notebooks表示笔记本2、点击【搜索】-【下载】(game表示游戏驱动)-【下载】3、双击运行exe文件4、使用邮箱注册账号时注意要设置正常的年龄PS设置1、设置PS使用GPU处理:点击【......
  • 3-使用@task设置测试用例执行的权重
    多个测试链路压测使测试任务按预想的比例执行locust的@task装饰器提供了入参weight,locust执行测试任务时,会根据weight的比例进行分配用户数fromlocustimporttask,HttpUserclassMyTestUser(HttpUser):#test_01:test_02=3:1@task(3)defweight_tes......
  • 怎么全局设置box-sizing
    box-sizing默认值为content-box,设置border和padding时会改变width和height并且不具有继承性,每次设置border或padding时都需要设置一遍box-sizing:border-box;比较麻烦可以这样子设置,就不需要每次写padding和border时都加box-sizing:border-box;了html{ box-sizing:bord......
  • linux日志轮替:日志轮替配置文件 | 设置日志轮替 | 日志轮替原理
    摘要介绍linux日志轮替logrotate原理及操作一、linux日志轮替日志轮替就是把旧的日志文件移动并改名,同时建立新的空日志文件,当旧日志文件超出保存的范围之后,就会进行删除目的是防止一个文件保存的日志太多:定时将日志文件的内容做好备份二、日志轮替文件命名centos7使......
  • linux防火墙:基本介绍 | 防火墙开启关闭 | 防火墙端口设置
    摘要介绍linux防火墙一、linux防火墙防火墙的基本原理,就是一堵墙,可以设置开启的端口和关闭的端口,但实际上比这复杂按我的理解,这个和计算机网络中的防火墙不是一回事计网当中的防火墙是指在局域网与外界相连的地方设置防火墙路由器,里面设置一套规则来抵制分组信息此处的防......