[백준 알고리즘/C++] 1931 회의실 배정

 

 

하나의 회의실에 최대 몇 개의 회의가 진행될 수 있는지 구하는 문제

 

왼쪽 열은 회의 시작시간, 오른쪽 열은 회의가 끝나는 시간이다 (첫 번째 줄 제외)

회의실이 하나이기 때문에 두 개의 회의가 동시에 진행될 수 없고,

한 회의가 끝난 동시에 다른 회의를 시작할 수 있다

 

가장 일찍 시작해서 가장 늦게 끝나는 경우도 있기 때문에 시작시간을 기준으로 삼으면 복잡해진다

가장 일찍 끝나는 회의를 기준으로 알고리즘을 시작해야한다

이런 생각을 한다면 자연스럽게 끝나는 시간을 기준으로 값을 정렬할 것이다..

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
struct Time {
    long long S;
    long long E;
};
 
int compare(Time& t1, Time& t2) {
    if (t1.E == t2.E) return t1.S < t2.S;
    else return t1.E < t2.E;
}
 
struct Time time[100001];
 
int main(void) {
    int n, answer = 0;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> time[i].S >> time[i].E;
    }
 
    sort(time, time + n, compare);
    long long start = 0, end = 0;
 
    for (int i = 0; i < n; i++) {
        if (time[i].S >= end) {
            start = time[i].S;
            end = time[i].E;
            answer++;
        }
        else continue;
    }
 
    cout << answer;
}

 

(저번 회의 끝나는 시간 <= 이번 회의 시작시간) 일 때 count 하면 됨