腾讯刷题 视野争夺

小Q在进行一场竞技游戏,这场游戏的胜负关键就在于能否能争夺一条长度为L的河道,即可以看作是[0,L]的一条数轴。

这款竞技游戏当中有n个可以提供视野的道具−真视守卫,第i个真视守卫能够覆盖区间[xi,yi]。现在小Q想知道至少用几个真视守卫就可以覆盖整段河道。

输入描述:

输入包括n+1行。

第一行包括两个正整数n和L(1<=n<=105,1<=L<=109)

接下来的n行,每行两个正整数xi,yi(0<=xi<=yi<=109),表示第i个真视守卫覆盖的区间。

输出描述:

一个整数，表示最少需要的真视守卫数量, 如果无解, 输出-1。

示例1

输入

4 6

3 6

2 4

0 2

4 7

输出

3

这道题考察的是贪心算法，首先将“真视守卫”按照左端从小到大，右端从大到小排列，设置两个变量，up更新的下限和mx本次视野的最右端，每次操作“真视守卫”时，将其最右端和up比较，如果小于等于则更新mx，反之更新up再将该真视守卫”进行比较操作

#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

struct node
{
    int l ,r;
    bool operator < (node b)
    {
        if(l == b.l)
        {
            return r > b.r;
        }
        return l < b.l;
    }
}a[201];

int main()
{
    int n, L;
    scanf("%d %d", &n, &L);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d", &a[i].l, &a[i].r);
    }
    sort(a, a+n);
    int up = a[0].r;
    int mx = a[0].r;
    int sum = 1;
    if(a[0].l > 0)
    {
        printf("-1\n");
        return 0;
    }
    for(int i=1;i<n;i++)
    {
        if(a[i].l <= up)
        {
            mx = max(a[i].r, mx);
            if(mx>=L)
            {
                printf("%d\n", sum+1);
                return 0;
            }
        }
        else
        {
            sum++;
            up = max(mx, up);
            i--;
        }
    }
    if(mx<L)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", sum);
    }
    return 0;
}