POJ-3190 : Stall Reservations

問題概要

N(<5*10^4)個の区間が与えられる。これを交わらないいくつかの列に分解したい。最小いくつにできるか復元付きで求める問題。

解法

左端の小さい順に貪欲にやればよい。左端でソートしてから右端のmin-heapに突っ込んでいけばよい。

acceptされたコード

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef int range_t;

struct Range {
	range_t from, to;
	int index;

	Range() {}
	Range(range_t from, range_t to, int index):from(from), to(to), index(index){}
};


bool cmpFrom (const Range& lhs, const Range& rhs) {
	return lhs.from < rhs.from;
}

struct CmpTo {
	bool operator() (const Range& lhs, const Range& rhs) {
		return lhs.to > rhs.to;
	}
};

const int MAX_N = 50000;

int N;
Range ranges[MAX_N];
int ans[MAX_N];

void init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		int from, to;
		scanf("%d%d", &from, &to);
		ranges[i] = Range(from, to + 1, i);
	}
}

void solve() {
	sort(ranges, ranges + N, cmpFrom);
	priority_queue<Range, vector<Range>, CmpTo> que;

	for (int i = 0; i < N; ++i) {
		if (que.empty() || ranges[i].from < que.top().to) {
			que.push(ranges[i]);
			ans[ranges[i].index] = que.size();
		}
		else {
			Range r = que.top(); que.pop();
			ans[ranges[i].index] = ans[r.index];
			que.push(ranges[i]);
		}
	}

	printf("%d\n", que.size());
	for (int i = 0; i < N; ++i) {
		printf("%d\n", ans[i]);
	}
}

int main() {
	init();
	solve();
	return 0;
}