[백준/BOJ] 9576. 책 나눠주기 [Gold 2]

9576. 책 나눠주기

문제출처 : https://www.acmicpc.net/problem/9576

code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(const pair<int, int>& a, const pair<int, int>& b)
{
	if (a.second != b.second)
		return a.second < b.second;
	return a.first < b.first;
}
int main()
{
	int N, M, testcase, answer = 0;
	cin >> testcase;

	while (testcase)
	{
		cin >> N >> M;
		int book[1001] = { 0 };
		answer = 0;
		vector<pair<int, int>> student(M);

		for (int i = 0; i < M; i++)
			cin >> student[i].first >> student[i].second;

		sort(student.begin(), student.end(), compare);

		int max = student[M - 1].second;
		int j = 0;

		for (int i = 0; i < M; i++)
			for (int j = student[i].first; j <= student[i].second; j++)
				if (book[j] == 0)
				{
					book[j] = 1;
					answer++;
					break;

				}
		cout << answer << '\n';
		testcase--;
	}
	return 0;
}

처음에 내림차순으로 정렬해서 범위가 큰 학생부터 나눠줄려고 하다보니 뒤에 범위가 작은 학생들에게는 못나눠주는 상황이 있어 오류가 났다. 그래서 오름차순으로 정렬후, 범위 안에있는 학생들에게 하나씩 나눠주면 된다 (어차피 시간제한도 n2이라 넉넉함)