第六章贪心(一)：区间问题的应用

AcWing 111. 畜栏预定

题目

有 N 头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定 N 头牛和每头牛开始吃草的时间 A 以及结束吃草的时间 B，每头牛在 [A,B] 这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式

第 1 行：输入一个整数 N。

第 2…N+1 行：第 i+1 行输入第 i 头牛的开始吃草时间 A 以及结束吃草时间 B，数之间用空格隔开。

输出格式

第 1 行：输入一个整数，代表所需最小畜栏数。

第 2…N+1 行：第 i+1 行输入第 i 头牛被安排到的畜栏编号，编号是从 1 开始的 连续 整数，只要方案合法即可。

数据范围

1≤N≤50000,
1≤A,B≤1000000

解答

属于区间分组问题，直接使用区间分组的模板代码，不过题目增加了要求，需要输出每个牛被安排的组号，增加一些额外的数组记录序号即可。

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

pair<PII, int> interval[N];

/*
struct Interval
{
    int left, right;
    // 定义排序规则:按左端点排序
    bool operator<(const Interval &it)const
    {
        return left < it.left;
    }
}interval[N];
*/

bool cmp(pair<PII, int> A, pair<PII, int> B)
{
    return A.first.first < B.first.first;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        interval[i].first={l, r};
        interval[i].second = i;
    }
    
    sort(interval, interval + n, cmp);
    
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆：保存分组的区间的最右端点
    
    int num = 0;
    int id[N];
    // 按照左端点从左到右遍历区间
    for(int i=0; i<n; i++)
    {
        auto it=interval[i].first;
        // 如果区间与已有区间冲突则开新组；否则更新已有组的max_r 
        if(heap.empty() || heap.top().first >= it.first)
        {
            num ++;
            PII temp = {it.second, i};
            heap.push(temp);
            id[i] = num;
        }else{
            id[i] = id[heap.top().second];
            heap.pop();
            PII temp = {it.second, i};
            heap.push(temp);
        }
    }
    
    printf("%d\n", heap.size());
    int result[N];
    for(int i = 0; i < n; i++)
    {
        result[interval[i].second] = id[i];
    }
    for(int i = 0 ; i < n; i++) printf("%d\n", result[i]);
    return 0;
}