백준 1931

4주차-4)

회의실 배정

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

---

 

벡터 컨테이너를 이용하여 풀이함.

벡터 컨테이너 meeting에 각 회의의 끝나는 시간과 시작 시간을 pair로 묶어서 넣어줌.

sort함수를 이용하며 저장된 회의 시간을 정렬함.

끝나는 시간을 첫 요소로 넣어주어기 떄문에 끝나는 시간이 짧은 회의들이 앞쪽에 오게되고 같은ㄹ 경우 시작 시간이 작은 회의 순서로 정렬된다.

 

회의가 끝나는 시간을 변수에 저장해 주고 meeting 에 저장된 순서로 꺼내 시작 시간이 저번 회의의 끝나는 시간보다 이후라면 count를 증가시키고 회의가 끝나는 시간을 업데이크 시켜줌

 

 

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

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

    int num;
    cin >> num;

    vector<pair<int, int>> meetings(num); // (end, start) 형태로 저장

    for (int i = 0; i < num; ++i) {
        int start, end;
        cin >> start >> end;
        meetings[i] = { end, start };
    }

    // 회의를 종료 시간 기준으로 정렬, 종료 시간이 같으면 시작 시간 기준으로 정렬
    sort(meetings.begin(), meetings.end());

    int count = 0;
    int lastEndTime = 0;

    for (const auto& meeting : meetings) {
        if (lastEndTime <= meeting.second) { // 회의의 시작 시간 검사
            count++;
            lastEndTime = meeting.first; // 종료 시간 업데이트
        }
    }

    cout << count;
    return 0;
}