[BOJ / C++] #1931 회의실 배정

🔮 문제 풀이

(시작시간, 끝나는 시간)을 갖는 구조체로 입력값을 저장한다.
이후 끝나는 시간을 기준으로 오름차순 정렬하고, 선택한 이전 끝나는 시간과 가장 가까운 시작시간(이전 끝나는 시간보다 크거나 같은)을 가진 것을 순차적으로 선택하여야 한다.

예를 들어

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

의 입력의 경우, 끝나는 시간으로 정렬 되어있다.
따라서 (1,4) -> (5,7) -> (8,11) -> (12,14) 순으로 선택할 수 있다.

구조체

struct Time{
    int s; //시작 시간
    int t; // 끝 시간
    Time(int a, int b){
        s=a;
        t=b;
    }
    bool operator<(const Time &b )const{
        if(t!=b.t) return t<b.t; //오름차순
        return s<b.s;
    }
};

💡 구조체 정렬하는 방법 주의

🔮 코드

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

struct Time{
    int s; //시작 시간
    int t; // 끝 시간
    Time(int a, int b){
        s=a;
        t=b;
    }
    bool operator<(const Time &b )const{
        if(t!=b.t) return t<b.t; //오름차순
        return s<b.s;
    }
};

int main(){

    int N;
    vector<Time> meetings;
    cin>>N;
    for(int i=0;i<N;i++){
        int s,t; cin>>s>>t;
        meetings.push_back(Time(s,t));
    }
    sort(meetings.begin(), meetings.end());


    int beforeT=meetings[0].t;
    int cnt=1;

    for(int i=1;i<N;i++){
        int curS=meetings[i].s;
        int curT=meetings[i].t;

        if(curS>=beforeT){
            cnt++;
            beforeT=curT;
        }
    }

    cout<<cnt<<"\n";
}