贪心算法区间问题——选择不想交区间-蒲公英云

贪心算法区间问题——选择不想交区间

た入场券 2022-05-09 07:04 379阅读 0赞

选择不想交的区间。

数轴上有n个区间（ai,bi）。选择尽可能多个区间，使得这些区间没有公共点。

分析：

  首先明确一个问题：假设有两个区间x,y，区间x完全包含y。那么，选x是不划算的，因为x和y最多选一个，选x不如选y，这样区间数目不会减少，而且给其他区间留下更多的位置。接下来，按照bi从小大大的顺序给区间排序。贪心算法策略是：**一定要选第一个区间**。为什么呢？
  现在区间已经排序成b1<=b2<=......<=bn了，考虑a1和a2的大小关系。
  情况一：a1>a2，如图a所示。包括之后所有被a1包含的区间都不选。
  情况二：如图（b）所示，非完全相交。黑色部分木有什么影响，但灰色部分被下一个区间包含。由上面知，选第一个。

题目：https://blog.csdn.net/xia842655187/article/details/51944718

描述
学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。

输入
第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(n<1000)表示该测试数据共有n个活动。
随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)

输出
对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行
样例输入
2
2
1 10
10 11
3
1 10
10 11
11 20
样例输出
1
2

提示
注意：如果上一个活动在t时间结束，下一个活动最早应该在t+1时间开始

-—————————— 本文来自 xia842655187 的CSDN 博客，全文地址请点击：https://blog.csdn.net/xia842655187/article/details/51944718?utm\_source=copy

代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=20;
struct timetable
{
    int a;
    int b;
}time[maxn];
bool comp(timetable &x,timetable &y)//多看两遍 
{
    if(x.b!=y.b)
        return (x.b<y.b);
    if(x.a!=y.a) 
        return (x.a<y.b);
}
int main()
{
    int i,n,count;
    while(cin>>n)
    {
        count=1;
        for(i=0;i<n;i++)//输入 
        {
            cin>>time[i].a;
            cin>>time[i].b;
        }
        sort(time,time+n,comp);//按b从小到大排序
        int newend=time[0].b;
        cout<<"("<<time[0].a<<","<<time[0].b<<")"<<"  "; //第一个必然是 
        for(i=1;i<n;i++)
        {
            if(newend<time[i].a)
            {
                count++;
                newend=time[i].b;
                cout<<"("<<time[i].a<<","<<time[i].b<<")"<<"  ";
            }    
        }
        cout<<endl<<count<<endl;     
    }
    return 0;
}