区间贪心

迭代盆景
• 阅读 1678

区间贪心

1.区间不相交问题

给出 N 个开区间(x, y),从中选择尽可能多的开区间,使得这些开区间两两没有交集。例如对于开区间(1, 3)、(2, 4)、(3, 5)、(6, 7)来说,可以选出最多三个区间(1, 3)、(3, 5)、(6, 7),它们之间没有交集。

思路分析

  • 最简单的情况(如图a),如果开区间 I1 被开区间 I2 包含,则选择 I1 是最好的选择,如果选择了 I1 ,就会有更大的区间如容纳其他开区间。
  • 将所有的开区间按左端点x从大到小排序,如果去掉区间包含的情况,那么一定会有 y1 > y2 > ... > yn 成立,如图b。可以看出I1的右边一段一定不会和其他区间重叠的,如果把它去掉,那么I1的左边的剩余部分就会被I2包含,因此应该选择 I1 。最终总是先选择左端点最大的区间。

区间贪心

代码

#include <cstdio> 
#include <algorithm>
#include <climits>

using namespace std;

const int N = 110;

struct Interval
{
    int x, y;
    bool operator< (const Interval &a) const
    {
        if (a.x != x) return x > a.x;
        else return y < a.y;
    }
    
}I[N];

int main()
{
    int n;

    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++)
            scanf("%d%d", &I[i].x, &I[i].y);
    
    sort(I, I + n);
    
    int ans = 1, lastX = INT_MAX;
    for (int i = 0; i < n; i ++)
        if (I[i].y <= lastX)
        {
            lastX = I[i].x;
            ans ++;
        }
    
    printf("%d\n", ans);
    
    return 0;
}

2.区间选点问题

给定 N 个闭区间[x, y],求最少需要确定多少个点,才能使每个闭区间中都至少存在一个点。

思路分析

如果闭区间I1被闭区间I2包含,那么在I1中的点一定包含在I2中。将所有区间按左端点由大到小排序,接下来只取左端点,这样这个点就能覆盖尽可能多的区间。

代码

只需将上文代码中的I[i].y <= lastX改为I[i].y < lastX即可。
原因:在区间不相交问题中,区间使开区间,当端点重合时,两个区间并没有相交。在本问题中,区间是闭区间,端点重合时,当前区间一定包含上一个区间的左端点,因此可以忽略当前区间。

#include <cstdio> 
#include <algorithm>
#include <climits>

using namespace std;

const int N = 110;

struct Interval
{
    int x, y;
    bool operator< (const Interval &a) const
    {
        if (a.x != x) return x > a.x;
        else return y < a.y;
    }
    
}I[N];

int main()
{
    int n;

    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++)
            scanf("%d%d", &I[i].x, &I[i].y);
    
    sort(I, I + n);
    
    int ans = 1, lastX = INT_MAX;
    for (int i = 0; i < n; i ++)
        if (I[i].y < lastX)
        {
            lastX = I[i].x;
            ans ++;
        }
    
    printf("%d\n", ans);
    
    return 0;
}
参考资料《算法笔记》.
点赞
收藏
评论区
推荐文章
blmius blmius
4年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
美凌格栋栋酱 美凌格栋栋酱
7个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Jacquelyn38 Jacquelyn38
4年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
2021年全球公有云终端用户支出将增长18% ;EMNLP 2020最佳论文:无声语音的数字发声
!(https://static001.geekbang.org/infoq/af/af9f6637b50b09be60b00a42f3812d5e.png)开发者社区技术周刊又和大家见面
可莉 可莉
3年前
2021年全球公有云终端用户支出将增长18% ;EMNLP 2020最佳论文:无声语音的数字发声
!(https://static001.geekbang.org/infoq/af/af9f6637b50b09be60b00a42f3812d5e.png)开发者社区技术周刊又和大家见面
Wesley13 Wesley13
3年前
Java 生成随机数
Java中常用的两种产生随机数的方法一、java.lang.Math类中的random()方法;调用这个Math.random()函数能够返回带正号的double值,该值大于等于0.0且小于1.0,即取值范围是\0.0,1.0)的左闭右开区间,返回值是一个伪随机选择的数,在该范围内(近似)均匀
Wesley13 Wesley13
3年前
Java日期时间API系列23
  有时候,往往需要统计某个时间区间的销量等问题,这就需要准确的起始时间,获取准确开始时间00:00:00,获取准确结束时间23:59:59。下面增加了一一些方法,获取当天起始时间,昨天起始时间,当前月第一天开始时间,当前月最后一天结束时间,上个月第一天开始时间,上个月最后一天结束时间,某个指定月的起始结束时间等等。其中月份最后一天往往因为月份不同和
Stella981 Stella981
3年前
AI 科学家带你快速 Get 人工智能最热技术
!(https://pic3.zhimg.com/80/v2af9f6637b50b09be60b00a42f3812d5e_1440w.jpg)日前,京东智联云与贪心学院联合举办的人工智能前沿技
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这