整数区间和活动安排问题

1001-高同学

发表文章数:265

首页 » LeetCode » 正文

为什么笔者把这两个题目放一起呢?因为笔者觉得都是牵扯到区间问题,而且区间问题相对于初学者有点难度和抽象,多对区间问题进行总结其实就会发现区间问题的题目主要在考对于区间的排序和区间之间相互包含的理解。

关于活动安排问题,可以点击这里

整数区间问题,网上有很多图解,这里就不在放图解了。网上的图解其实有点难懂,我当时看的时候一脸懵,这都是啥啊,所以我准备用简单易懂的话进行该题分析

 

整数区间:选一个区间,使该区间满足包含所有区间的同时,元素最少。

实际上就是对每个区间进行排序,该区间(记为A)最左边的点是否在下一个区间(记为B)内。
如果在(即A B 相交),那么继续判断下下一个区间(记为C);如果不在(即A B 不相交),则就要把元素数+1,在将下一个区间最左边的点(即区间B)与下下一个区间最右边的点(即区间A)进行比较,再按照上述的方法进行选择。

整数区间代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1500;
struct node
{
    int beginTime;
    int endTime;
    node()
    {
        beginTime=0;
        endTime=0;
    }
}a[maxn];
bool cmp(node a,node b)
{
    if(a.endTime!=b.endTime)
        return a.endTime<b.endTime;
    if(a.endTime==b.endTime)
        return a.beginTime<b.beginTime;
}

int main()
{
    int n,i;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>a[i].beginTime>>a[i].endTime;
    }
    sort(a+1,a+1+n,cmp);
    int cnt=0;
    int tmp=-1;
    for(i=1; i<=n; i++)/*kai shi jinxing huo dong xuan ze */
    {
        if(a[i].beginTime <= tmp)
        {
            continue;
        }else
        {
            cnt++;
            tmp=a[i].endTime;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

 

 

 

 

 

 

 

 

 

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《整数区间和活动安排问题》 发布于2019-06-06

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录