[C++] 백준 온라인 저지 1931번 회의실 배정 풀이

회의실 한 개로 최대한 많은 회의를 하려고 한다. 

각 회의가 겹치지 않으면서 최대한 많이 할 수 있는 회의 수를 찾는 문제

 

---

문제의 조건

 

1. 총 회의 갯수 N이 주어진다. 

 

2. 다음 줄부터 각 회의의 시작 시간과 종료시간이 주어진다. 

 

3. 가능한 회의의 최댓값 출력 

 

---

풀이 과정

 

현재 진행 중인 회의의 종료 시간보다 다음 회의의 시작 시간이 같거나 크다면 정답 수에 포함시키는 방식으로 코드를 짰습니다.

 

하지만...

처음엔 예제의 답이 마치 정렬을 하지 않고 주어진 순서 그대로 푸는 것 처럼 보여서...

정렬을 하지 않은 상태로 위의 알고리즘을 적용했더니 틀림 ㅠ.ㅠ

 

예제를 보면 아시겠지만 정렬을 하지 않는다고 충분히 오해할 만한 내용이지 않나요????

내가 아직 경험이 짧아서 그런 것인지..흑흑

 

암튼 또 질문 게시판을 열심히 검색해서 반례를 찾았고 종료 시간 기준으로 오름차순 정렬을 해 주어야 한다는 것을 알았습니다. 

 

 

그래서 수정한 풀이

 

1. 회의 종료 시간이 짧은 순서대로 오름차순 정렬을 하는데

시작 시간이 같다면 시작 시간이 빠른 순서대로 오름차순 정렬을 한다. 

 

2. 정렬이 끝나면 반복문을 돌려서 현재 진행중인 회의의 종료 시간보다 다음 회의의 시작 시간이 크거나 같으면 

현재 회의를 다음 회의로 교체하고 정답 수를 증가시킨다. 

 

---

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    //2차원 배열의 각 원소의 0번째 인덱스엔 시작시간, 1번째 인덱스엔 종료시간 
    vector<vector<int>> meetings;
    for (int i = 0; N > i; i++)
    {
        int start, end;
        cin >> start >> end;
        vector<int> v;
        v.emplace_back(start);
        v.emplace_back(end);
        meetings.emplace_back(v);
    }
    
    //정렬 비교식은 람다식으로 작성 
    sort(meetings.begin(), meetings.end(), [](const vector<int>& a, const vector<int>& b)->bool {
        if (a[1] < b[1])
            return true;
        if (a[1] == b[1] && a[0] < b[0])
            return true;
        return false;
    });
    
    //최소한 가장 앞에 있는 회의는 진행할 것이기 때문에 정답은 1부터 시작 
    int answer = 1;
    int curStart = meetings[0][0];
    int curEnd = meetings[0][1]; //시작과 종료 시간을 0번째 회의로 초기화 한 상태에서 시작
    for (int i = 1; meetings.size() > i; i++)
    {
        if (curEnd <= meetings[i][0])
        {
            curStart = meetings[i][0];
            curEnd = meetings[i][1];
            answer++;
        }
    }
    
    cout << answer;
    
    return 0;
}