poj 3190

// poj 3190.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <queue>
#include <vector>
//#include <unordered_map>
#include <algorithm>

using namespace std;


/*
Input
Line 1: A single integer, N
Lines 2..N+1: Line i+1 describes cow i‘s milking interval with two space-separated integers.
Output
Line 1: The minimum number of stalls the barn must have.
Lines 2..N+1: Line i+1 describes the stall to 
which cow i will be assigned for her milking period.
Sample Input

5
1 10
2 4
3 6
5 8
4 7
Sample Output

4
1
2
3
2
4
*/


struct COW {
	int start;
	int end;
	int num;
	int stall;
};


struct cmp {
	bool operator()(struct COW& x, struct COW& y)
	{
		return  x.end > y.end;
	}
};

priority_queue<struct COW, vector<struct COW>, cmp> q;    //定义方法
int n;
 

bool cmp_COW(const struct COW& a, const struct COW& b) {
	return a.start < b.start;
}

struct COW mm[1000010];

int main()
{
	cin >> n;
	vector<struct COW> arr;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		struct COW t; t.start = a; t.end = b; t.num = i;
		arr.push_back(t);
	}

	sort(arr.begin(), arr.end(),cmp_COW);

	int ans = 0;
	//unordered_map<int, struct COW> mm;

	for (int i = 0; i < arr.size(); i++) {
		if (q.empty() || q.top().end >= arr[i].start) {
			ans++;
			arr[i].stall = ans;
			q.push(arr[i]);
		}
		else {
			struct COW t = q.top();
			mm[t.num] = t;
			q.pop();
			arr[i].stall = t.stall;
			q.push(arr[i]);
		}
	}
	
	cout << ans << endl;

	while (!q.empty()) {
		struct COW t = q.top();
		mm[t.num] = t;
		q.pop();
	}

	for (int i = 0; i < n; i++) {
		cout << mm[i].stall << endl;
	}
	
	return 0;
}

poj 3190

原文：https://www.cnblogs.com/itdef/p/15100554.html