[BOJ/C++] 회의실 배정(1931번)

1. 개요

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

1931번: 회의실 배정

1-1. 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대해 회의실 사용표를 만드려고 한다. 각 회의 l에 대해 시작 시간과 끝나는 시간이 주어지며, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾는 프로그램을 작성한다. 여기서 한 회의가 끝남과 동시에 다음 회의가 시작될 수 있다. 즉, 회의 시작시간과 끝나는 시간이 같을 수 있다. 

1-2. 제한 사항

 - 첫 줄에 회의 N이 주어지며, N은 1 이상 100,000 이하

 - 둘째 줄부터 N+1줄 까지 각 회의의 정보가 주어지며, 시작 시간과 끝나는 시간이 주어짐

 - 시간은 2^31-1 이하 자연수 또는 0 

---

2. 구현

2-1. 풀이

회의의 최대 개수이므로, 끝나는 시간을 정렬해 다음 시작시간과 비교하며 +1 해주면 된다. 

2-2. 코드 

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


constexpr size_t MAX_NUM = 100000;

struct Time {
    int start, end;
};

Time lists[100000];

bool compare(const Time& a, const Time& b) {
    if (a.end == b.end) return a.start < b.start;
    return a.end < b.end;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N, result = 1;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> lists[i].start >> lists[i].end;
    }

    sort(lists, lists + N, compare);

    Time cur = lists[0];
    for (int i = 1; i < N; i++) {
        if (cur.end <= lists[i].start) {
            result += 1;
            cur = lists[i];
        }
    }
    cout << result;
    return 0;
}