1931: 회의실 배정

 📃 문제: 백준 1931(회의실 배정)

1931번: 회의실 배정

[문제] 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

[입력] 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

 

🥈 난이도: 실버 1

 

 

😲 사용한 개념: 그리디 알고리즘

 

💡 그리디 알고리즘이란?

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 결과에서의 최선의 선택지라고 가정하는 알고리즘이다.

최적해를 구하는 근사적인 방법으로 당장 눈 앞에 있는 최적의 해를 선택해가는 방식으로 진행되기 때문에 탐욕적인(=Greedy) 알고리즘이라고 불린다.

 

수행과정은 아래와 같다.

1) 현재 상태에서의 최선의 해를 선택
2) 해가 전체 문제 제약 조건에 벗어나지 않는지 검사
3) 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 아니라면 1로 돌아가 동일 작업을 반복.

 

 

📖 풀이 사고 과정

 

 

 

 

👩‍💻 구현 코드(c++ 사용)

 

🐸시간복잡도 개선 코드(O(n*logn))🐸

//시간복잡도 O(n*logn) 버전
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Meeting {
    int start;
    int end;
};

bool compare(Meeting a, Meeting b) {
    if (a.end == b.end) {
        return a.start < b.start;
    }
    return a.end  <  b.end;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;

    cin >> N;
    vector<Meeting> meetings(N);
    
    for (int i = 0; i < N; i++) {
        cin >> meetings[i].start>>meetings[i].end;
    }
    sort(meetings.begin(), meetings.end(), compare);
    int endTime = 0, cnt=0;
    for (int i = 0; i < N; i++) {
        if (endTime <= meetings[i].start) {
            endTime = meetings[i].end;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

 

 

 

🐾시간초과 난 코드(O(n**2))🐾

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    
    int N, start, end, cnt=0, pop_index=-1;
    cin >> N;
    vector<int> startArr;
    vector<int> endArr;

    for (int i = 0; i < N; i++) {
        cin >> start >> end;
        startArr.push_back(start);
        endArr.push_back(end);
    }

    int endTime = INT_MAX;
    for (int i = 0; i < N; i++) {
        if (endTime > endArr[i]) {
            endTime = endArr[i];
            pop_index = i;
        }
    }
    cnt++;
    startArr.erase(startArr.begin() + pop_index);
    endArr.erase(endArr.begin() + pop_index);

    int continue_flag = true;
    while (continue_flag) {
        int nextEndTime = INT_MAX;
        continue_flag = false;
        for (int i = 0; i < startArr.size(); i++) {
            if (endTime <= startArr[i] && endArr[i] < nextEndTime) {
                nextEndTime = endArr[i];
                pop_index = i;
                continue_flag = true;
            }
        }
        if (continue_flag) {
            cnt++;
            startArr.erase(startArr.begin() + pop_index);
            endArr.erase(endArr.begin() + pop_index);
            endTime = nextEndTime;
        } 
    }
    
    cout << cnt << endl;
    return 0;
}