(C++) 백준 1931번 - 회의실 배정

문제 링크 : https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

문제 풀이

그리디 알고리즘을 활용한 문제이다.

회의실을 사용할 수 있는 회의의 개수를 최대로 하기 위해선 종료 시간이 가장 이른 순으로 사용하게 하면 된다.

그렇기에 회의가 종료되는 시간의 오름차순으로 정렬을 해놓고 시작 시간이 지나지 않은 가장 빠른 회의가 회의실을 사용하도록 하면 된다.

#include <iostream>
#include <algorithm>
#define X first
#define Y second

using namespace std;

pair<int,int> meetings[100005];
int n, cnt, cur, mn;

bool compare(pair<int,int>a, pair<int,int>b){
    if(a.Y != b.Y) return a.Y < b.Y;
    else return a.X < b.X;
}

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

    int x, y;
    for(int i = 0; i < n; i++){
        cin >> x >> y;
        meetings[i] = {x,y};
    }
    sort(meetings, meetings+n, compare);
    int cur = 0;
    for(int i = 0; i < n; i++){
        if(cur > meetings[i].X) continue;
        cur = meetings[i].Y;
        cnt++;
    } 
    cout << cnt;
}