[백준 1931번 C/C++] 회의실 배정

 

 

목차

 

 

---

 

 

[백준 1931번 C/C++] 회의실 배정

 

 

 

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

1931번: 회의실 배정

---

 

해결전략

 

Greedy Algorithm 탐욕 알고리즘

 

 

---

 

첫번째 풀이 - 시간 초과

 

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

int n, a, b, answer, maxDay = -1, maxValue = -1;

struct Data
{
    int start, end;

    Data(int a, int b) { start = a; end = b; }

    bool operator<(const Data& other) const {
        return end != other.end ? end < other.end : start<other.start;
    }
};

vector<Data> v;

int DFS(const vector<Data>& v, int idx, int end)
{
    while (idx < v.size() && v[idx].start < end) {
        idx++;
    }

    if (idx >= v.size()) {
        // 더 이상 회의가 없으면 종료
        return 0;
    }

    // 현재 회의를 선택한 경우
    int go = 1 + DFS(v, idx + 1, v[idx].end);
    // 현재 회의를 선택하지 않은 경우
    int stop = DFS(v, idx + 1, end);

    // 두 경우 중 더 큰 값을 반환
    return max(go, stop);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        v.push_back(Data(a, b));
    }
    sort(v.begin(), v.end());

    answer = DFS(v, 0, 0);

    cout << answer;

    return 0;
}

DFS는 시간초과가 나왔다.

---

 

 

 

코드

 

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

struct Meeting {
    int start, end;
};

//회의가 끝나는 시간을 기준으로 정렬하고, 
//같은 종료 시간의 경우 시작 시간을 기준으로 정렬
bool comp(const Meeting& a, const Meeting& b) {
    if (a.end == b.end)
        return a.start < b.start;
    return a.end < b.end;
}

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

    int n;
    cin >> n;
    vector<Meeting> v(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i].start >> v[i].end;
    }

    sort(v.begin(), v.end(), comp);

    int cnt = 0;
    int last_end = -1;
    for (const auto& mt : v) {
        if (mt.start >= last_end) {
            cnt++;
            last_end = mt.end;
        }
    }

    cout << cnt << '\n';

    return 0;
}

 

회의가 끝나는 시간을 기준(v[i].end)으로 정렬한다. 같은 종료 시간의 경우 시작 시간을 기준으로 정렬한다.

겹치지 않는 회의를 순차적으로 선택하면서 카운트한다.

가장 많은 회의가 몇 개 선택되는지 출력한다.

 

 

입력이 다음과 같다면

전체 미팅 수: 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
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

mt.start		1	5	8	12
last_end	-1	4	7	11	14

 

 

 

입력이 다음과 같다면

전체 미팅 수:4
1 5
0 3
2 2
2 2

 

정렬된 값은 다음과 같다.

2 2
2 2
0 3
1 5

 

mt.start		2	2
last_end	-1	2	2

 

---

 

 

 

다시 풀어봄

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

int n;
vector<pair<int, int>> v;

bool Comp(pair<int, int>&a, pair<int, int>&b)
{
	if (a.second == b.second)
		return a.first < b.first;
	
	return a.second < b.second;
}

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

	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++){
		cin >> v[i].first >> v[i].second;
	}

	sort(v.begin(), v.end(), Comp);

	for (int i = 0; i < n; i++)
		cout << v[i].first << " " << v[i].second << "\n";

	int cnt = 0;
	int last_end = -1;
	for (int i = 0; i < n; i++)
	{
		if (v[i].first >= last_end) {
			cnt++;
			last_end = v[i].second;
		}

	}

	cout << cnt;

	return 0;
}

 

 

핵심 아이디어

	int cnt = 0;
	int last_end = -1;
	for (int i = 0; i < n; i++)
	{
		if (v[i].first >= last_end) {
			cnt++;
			last_end = v[i].second;
		}

	}

 

 

 

 

 

 

 

다른 사람 풀이

 

https://cocoon1787.tistory.com/147

[C/C++] 백준 1931번 - 회의실 배정 (그리디 알고리즘)