[BOJ/C+]#1931会議室手配

9503 ワード
greedy ps boj テキストリンク


🔮 問題を解く


入力値を(開始時間、終了時間)を持つ構造体として保存します.
その後は끝나는 시간을 기준으로 오름차순 정렬となり、選択した前の終了時間と最近の開始時間(前の終了時間以上)とが順に選択される.
例:
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";
}
132. loop
モジュール