[贪心] UVa1617 笔记本 （推理）

题目

思路

这道题我的思路好像跟别人的不太一样。

首先，区间按终点排序，终点相同按起点。

随后对于每一个区间，执行如下操作：

(1)查找 A[i].a−1 A[i].b−1 A [ i ] . a − 1   A [ i ] . b − 1 范围内，有没有已经被占用的时间段。如果有，那么这个时间段后面紧接的时间段是否是空闲，是的话在此插入。（代码是A[i].a是因为数据结构不同）

(2)没找见(1)这种的，那就直接从A[i].b找到1，有空闲的插入。

注意此处，我刚开始是从A[i].b找到A[i].a，而且这样说起来也合理，但是如果是下面这种情况。

就会在最小的区间那找不到解。

可能有人会想到，那让终点相同时起点降序排列。那又会导致这种情况：

导致不是最优解。（最优解应该是没有空隙的）

那么方法就是，既然这道题必有解，那么就直接让最短的区间，从终点一直向前遍历，找到有空的插入即可。我无法判断这正确性，但AC了。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define _for(i,a,b) for(int i = (a); i<(b); i++)
#define _rep(i,a,b) for(int i = (a); i<=(b); i++)
using namespace std;

const int maxn =  + ;
const int maxx =  + ;
int n;
bool G[maxx];
struct segment {
    int a, b;
    bool operator < (const struct segment &rhs) const {
        return b<rhs.b || (b == rhs.b && a<rhs.a);
    }
}A[maxn];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        _for(i, , n) scanf("%d%d", &A[i].a, &A[i].b);
        sort(A, A + n);
        memset(G, , sizeof(G));

        _for(i, , n) {
            bool success = false;
            _rep(j, A[i].a, A[i].b - )
                if (G[j] && !G[j + ]) {
                    G[j + ] = true;
                    success = true;
                    break;
                }
            if (!success)
                for (int j = A[i].b; j >= ; j--)
                    if (!G[j]) {
                        G[j] = true;
                        break;
                    }
        }

        int ans = ;
        _for(i, , A[n - ].b + )
            if (G[i] == false &&  G[i-] == true)
                ans++;
        ans--;
        printf("%d\n", ans);
    }
    return ;
}