백준 9576

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

이 문제를 유니온 파인드와 그리디 로 풀려했는데 이상하게 계속 에러가 나서 그냥 유니온 파인드 안하고 순차로 검사하도록 바꾸니 정답이었다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int t, n, m;
bool check[1001];  // 책 배정 여부를 나타내는 boolean 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while (t--) {
        cin >> n >> m;
        vector<pair<int, int>> students(m);

        // check 배열 초기화
        fill(check, check + n + 1, false);

        // 입력받기
        for (int i = 0; i < m; i++) {
            cin >> students[i].first >> students[i].second;
        }

        sort(students.begin(), students.end(), [](pair<int, int> a, pair<int, int> b) {
            if (a.second == b.second) return a.first < b.first;
            return a.second < b.second;
            });

        int cnt = 0;

        for (auto student: students) {
            int a = student.first;
            int b = student.second;
            for (int j = a; j <= b; j++) {  // a부터 b까지 탐색
                if (!check[j]) {  // 배정되지 않은 책이라면
                    check[j] = true;  // 책 배정
                    cnt++;
                    break;
                }
            }
        }

        cout << cnt << "\n";  // 정답 출력
    }

    return 0;
}

이 문제는 결국에 가장 책을 먼저 배정 하는게 목표이다 이에 b를 기준으로 오름 차순 해주고 b가 같다면 a를기준으로 오름차순 해주면서 결국에는 어떤 부분까지 책을 일찍 배정해줌으로서 배정해주는 문제이다