17. UVa-11926 Multitasking

문제

<그림1: 문제설명>

문제는 긴데 그냥 칼렌더 채우라는 거, 내 풀이가 좋은 지는 잘 모르겠음. 굳이 1000000개의 bitset을 써야하나 싶지만 competitive algorithm책에서는 그런 방법의 풀이를 제시하고 있음

 

#include<iostream>
#include<bitset>
using namespace std;

int main() {
	int n, m,s,e,r;
	bool conflict;
	bitset<1000001> schedules;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) break;//terminal case
		schedules.reset();
		conflict = false;
		for (int i = 0; i < n; i++) { // one time task
			cin >> s >> e;
			for (int j = s; j < e; j++) {
				if (schedules[j] == 1) conflict = true;
				else schedules[j] = 1;
			}
		}
		for (int i = 0; i < m; i++) {
			cin >> s >> e >> r;
			while (e <= 1000000) {
				for (int j = s; j < e; j++) {
					if (schedules[j] == 1) conflict = true;
					else schedules[j] = 1;
				}
				s += r;
				e += r;
			}
		}
		cout << ((conflict) ? "CONFLICT" : "NO CONFLICT")<<endl;

	}
	return 0;
}

아 참, 양끝 구간이 닫는 touch의 허용을 위해 칼렌더는 주어진 start time과 end time에 대해 [s,e)의 구간을 채우게했음.