1 문제

회의 시작 시간, 종료 시간을 입력받았을 때 최대로 회의를 많이 할 수 있는 숫자를 구하는 문제
문제 링크

2 구현

2.1 Idea

그리디 알고리즘으로 풀면 된다.
단, 입력을 받을 때 종료 시간, 시작 시간 순으로 sort를 해주면 된다.

2.1 Code

// https://www.acmicpc.net/problem/1931

#include <iostream>
#include <vector>

#include <algorithm> //std::sort

typedef struct{
    int start;
    int finish;
} meet;

bool compareMeet(const meet& a, const meet& b){
    if (a.finish > b.finish){
        return false;
    }
    else if ((a.finish == b.finish ) && (a.start > b.start)){
        return false;
    }

    return true;
}

int FindMaxMeeting(const std::vector<meet>& v, const int maxFinish){
    int maxMeeting = 1;
    int t = v[0].finish;

    for (int i=1; i<v.size(); ++i){
        if (v[i].start >= t){
            ++maxMeeting;
            t = v[i].finish;
        }
    }

    return maxMeeting;
}

int main(){
    unsigned int N = 0;

    std::cin >> N;

    //construct v
    std::vector<meet> v;

    int maxFinish = 0;
    for (unsigned int i=0; i<N; ++i){
        int _start = 0;
        int _finish = 0;

        std::cin >> _start >> _finish;

        v.push_back({_start, _finish});

        if (_finish > maxFinish){
            maxFinish = _finish;
        }
    }

    std::sort(v.begin(), v.end(), compareMeet);

    std::cout << FindMaxMeeting(v, maxFinish) << std::endl;

    return 0;
}