首页 > 代码库 > poj 1716 Integer Intervals

poj 1716 Integer Intervals

题目:
在数轴上有n个区间,每个区间都是连续的整数区间。现在要在数轴上任取一堆元素,构成一个集合V,要求每个区间和V的交集至少有两个不同的元素。求V的最小的元素个数。

问题分析:
      
可以使用贪心算法,最终结果肯定是小于大于2×n的,如果两个集合之间有相同的元素,那么选相同的元素必然会使结果更小,当我们以e排序后,如果有相同的必然是最后的元素。所以贪心的策略就是如果一个区间最后两个元素没被选就选上。

步骤:
先对所有区间按末端点排序。
取第i个区间的最后两个元素Selem和Eelem。
若第i+1个区间包含了这两个元素,则跳到下一个区间所取的元素个数+0
若第i+1个区间只包含了这两个元素中的一个(由于有序,所以必定是包含Eelem),则取第i+1个区间的最后一个元素,所取的元素个数+1。为了方便下一区间的比较,更新Selem和Eelem的值,使他们为当前V集合中最后的两个元素。
若第i+1个区间没有包含这两个元素,则第i+1个区间的最后两个元素,所取的元素个数+2。为了方便下一区间的比较,更新Selem和Eelem的值,使他们为当前V集合中最后的两个元素。
Selem初始化为第一个区间的最后倒数第2个元素,
Eelem初始化为第一个区间的最后的元素,
所取的元素个数初始化为2 (就是Selem和Eelem)。

#include <stdio.h>
#include <algorithm>

using namespace std;
const int M = 10005;

struct interval
{
    int s, e;
}inter[M];

bool cmp(interval x, interval y)
{
    return x.e < y.e;
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d %d", &inter[i].s, &inter[i].e);
        }
        sort(inter, inter+n, cmp);
        int Selem = inter[0].e-1, Eelem = inter[0].e;
        //取当前区间的两个元素,初始化为最后面两个
        int ans = 2; //至少取sum个元素才能保证每个区间至少含有其中的2个元素  
        for (int i = 1; i < n; i++)
        {
            if (Selem >= inter[i].s)  //前一个区间所取的两个元素都在当前区间内
                continue;
            else if (Eelem >= inter[i].s)  //前一个区间所取的只有一个元素在当前区间内 
            {
                Selem = Eelem;
                Eelem = inter[i].e;  //按序更新当前区间所取的两个元素:Selem与Eelem  
                ans += 1;   //Eelem是新取的一个元素 
            } 
            else        //前一个区间所取的没有一个元素在当前区间内
            {
                Selem = inter[i].e-1;  
                Eelem = inter[i].e;    //按序更新当前区间所取的两个元素:Selem与Eelem 
                ans += 2;         //Selem与Eelem是新取的两个元素
            }
        }
        printf("%d\n", ans);  
    }
    return 0;
}