1931

백준 1931번

Link: 1931번: 회의실배정

---

문제 설명

Greedy 알고리즘의 대표격인 문제다.

예전에 한번 풀어봤던것 같긴 한데 그때도 틀렸다.

마음 다잡고 다시한번 풀어봤는데, 답이 맞는것 같으면서도 계속 틀렸다고 나오더라.

어떤 부분에서 문제가 있나 해서 질문게시판 돌아다니면서 반례들을 찾아봤는데, 크게 2가지 문제가 있었다.

첫번째는 끝나는 시간이 같은 경우 시작하는 시간이 빠른 회의가 먼저 오도록 정렬되어야 한다는 점.

두번째는 배정 가능한 회의에 포함시킬때 그 회의를 포함하였음을 표시하여 중복으로 포함시켜선 안된다는 점.

첫번째 문제는 정렬 함수를 좀 바꿔서 해결했다.

두번째 문제는 방문 여부를 어떻게 표시할지 고민하다 1부터 2147483647까지의 bool형태의 배열을 만들까 해봤다.

용량이 용량이라 그런지 컴파일 자체가 안되더라.

어떻게할지 고민하다가 구조체에 방문 여부도 포함하도록 바꿔서 제출해보니 바로 맞았다.

Greedy나 BFS나 DFS나 방문여부 표시해주는게 참 중요한 것 같다.

몇년전부터 못풀던 문제였는데 오늘에서라도 풀어서 기분은 좋다.

---

정답 코드

//
// Created by Keith_Lee on 18/02/2019.
//

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

using namespace std;

struct meeting{
    int start, end;
    bool visit;
};

int N;

bool compare(meeting a, meeting b){
    if(a.end < b.end){
        return true;
    }
    else if(a.end == b.end){
        if(a.start < b.start){
            return true;
        }
    }
    return false;
}

int main(){
    cin >> N;

    vector<meeting> meetings;

    int start, end;

    for(int i=0; i<N; i++){
        cin >> start >> end;

        meetings.push_back({start, end, false});
    }

    sort(meetings.begin(), meetings.end(), compare);

    vector<meeting> available;
    available.push_back(meetings[0]);
    meetings[0].visit = true;

    for(int i=0; i<meetings.size(); i++){
        int currentEnd = available[available.size()-1].end;

        if(meetings[i].start >= currentEnd && !meetings[i].visit){
            available.push_back(meetings[i]);
        }
    }

    cout << available.size() << '\n';

    return 0;
}

---