POJ 2376

==>原题链接

题目概述

给定一些区间和要求覆盖的总长度，求能使整个长度完全被覆盖的最少的区间数。

思路

贪心。贪心策略是首先按照区间的左值记为x排序，x相等再按长度y - x排序。然后对于已排序的值，要删除某些无用的区间，例如序列中已有3 - 10，则 4 - 6， 5 - 7这样的区间都是无意义的，应该删去，实现的办法非常简单，只要维护一个最大的“尾部值”，只要有序区间序列按顺序扫一次，只要y值小于最大的尾部值mx，总是“无意义的”，可被删去。

数据被初始化后，利用 map 每次hash到以x为左值的长度最大的区间，反复循环，贪心得到最优解。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n, l, ans = 0;
bool f = true;

typedef struct
{
    int x, y;
} PIR;

PIR d[25000 + 10];
int map[100000];

void init();
bool cmp(PIR a, PIR b);
void solve();

int main()
{
    freopen("2376.in", "r", stdin);
    init();
    solve();
    if (f)
    {
        printf("%d\n", ans);
    }
    else
    {
        printf("-1\n");
    }

    return 0;
}

void init()
{
    int i, j;
    scanf("%d%d", &n, &l);
    for (i = 0; i < n; i++)
    {
        scanf("%d%d", &d[i].x, &d[i].y);
    }
    sort(d, d + n, cmp);
    j = 0;
    for (i = 0; i < n; i++)
    {
        if (d[i].x > j)
        {
            j = d[i].x;
            map[j] = i;
        }
    }
}

bool cmp(PIR a, PIR b)
{
    int d1 = a.y - a.x,
        d2 = b.y - b.x;
    if (a.x == b.x)
    {
        return d1 <= d2;
    }
    else
    {
        return a.x < b.x;
    }
}

void solve()
{
    int i, t, last_i;
    if (d[0].x > 1)
    {
        f = false;
        return;
    }

    t = d[0].y;
    ans++;
    i = t + 1;

    while(i < n)
    {
        if (map[i])
        {
            ans++;
            t = d[map[i]].y;
            last_i = i;
            i = t + 1;
        }
        else
        {
            while(!map[--i])
            {
                if (i == last_i)
                {
                    f = false;
                    return;
                }
            }

        }
    }
}