Poj 3190: Stall Reservations

題目

分析

這題被歸類在區間的部份，雖然我覺得跟區間沒那麼大關係，反而跟 最小化生產線 很像：

一條生產線有一台機器人，一次只能處理一件工作。現在有 N 個工作，必需依序執行，每件工作所需時間不同，求最少需要幾條生產線（幾台機器人）來完成所有工作。

解決方法是用 pirority_queue ，再加上 Greedy。

現在題目變成工作有起始時間、結束時間。原理不變，一樣使用 priority_queue ，再不斷地挑出可以 assign 的、目前完成時間最早的 Stall。

AC Code

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

struct Cow {
	int id;
	int start, end;
	
	bool operator < (const Cow& c) const {
		return start < c.start;
	}
	
};

struct Stall {
	int id;
	int end;
	
	Stall(int a, int b) {
		id = a;
		end = b;
	}
	
	bool operator > (const Stall& s) const {
		return end > s.end;
	}
};

Cow cows[50000];
int assign_to[50000];
int N;

int solve() {
	sort(cows, cows + N);
	
	priority_queue< Stall, vector<Stall>, greater<Stall> > pq;
	pq.push(Stall(1, cows[0].end));
	assign_to[cows[0].id] = 1;
	
	for (int i = 1; i < N; i++) {
		int min_end_time = pq.top().end;
		
		if (cows[i].start > min_end_time) {
			int id = pq.top().id;
			pq.pop();
			pq.push(Stall(id, cows[i].end));
			assign_to[cows[i].id] = id;
		}
		else {
			int id = pq.size() + 1;
			pq.push(Stall(id, cows[i].end));
			assign_to[cows[i].id] = id;
		}
		
		// cout << cows[i].id << ": " << assign_to[cows[i].id] << endl;
	}
	
	return pq.size();
}

int main() {
	ios::sync_with_stdio(false);
	
	cin >> N;
	for (int i = 0; i < N; i++)	{
		cows[i].id = i;
		cin >> cows[i].start >> cows[i].end;
	}
	
	cout << solve() << "\n";
	for (int i = 0; i < N; i++)
		cout << assign_to[i] << "\n";
	
	return 0;
}

amoshyc/poj3190.md

Poj 3190: Stall Reservations

題目

分析

AC Code