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; }