백준 9576(책 나눠주기)

https://www.acmicpc.net/problem/9576

9576번: 책 나눠주기

 

 

그리디로 푼 문제

 

책을 최대한 많이 나눠주려고 한다. 

 

책을 최대한 많이 못 나눠주게 되는 이유는 어떤 애한테 어떤 책을 줌으로써 다른 범위가 좁은 애가 못 받는 경우가 생겨서이다. 

 

방법은 절대 누군가는 가질수 없는 곳을 가진 사람을 가장 늦게 뽑게하자이다 

 

그러니깐 a b범위가 있을때, 

 

b를 기준으로 오름차순 정렬을 한뒤에 

 

b가 가장 앞선 사람부터 뽑게한다. 

 

1 2 

1 1

1 5 

2 6

3 5

4 5

2 3

 

을 정렬하면 

 

1 1

1 2

2 3

1 5

3 5 

4 5

2 6 이되고 

 

여기서 앞부터 조사를 한다. 

 

갖고 싶은 책 중에서 만약에 선택할 수 있는 책이 있으면 바로 준다. 

 

1 -> check[1] = true;

2 -> check[1] == true; -> check[2] = true;

3 ->

...

 

이런식으로 반복하게 된다면 책이 순서대로 나가게된다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 1001

int T, N, M, cnt;

int main() {
	cin >> T;
	while (T--) {
		vector<pair<int, int> > v;
		bool check[MAX] = { false };
		cnt = 0;
		cin >> N >> M;
		for (int i = 0; i < M; i++) {
			int start, fin;
			cin >> start >> fin;
			v.push_back(make_pair(fin, start));
		}
		sort(v.begin(), v.end());
		for (int i = 0; i < M; i++) {
			int start = v[i].second;
			int fin = v[i].first;
			for (int j = start; j <= fin; j++) {
				if (!check[j]) {
					check[j] = true;
					cnt++;
					break;
				}
			}
		}
		cout << cnt << "\n";
	}

}