백준 1931 (회의실 배정) c++

문제

1931번: 회의실 배정

회의의 시작시간과 끝시간이 주어지면 회의시간이 서로 겹치지 않게 최대 몇개의 회의가 진행될 수 있는지

알아보는 문제입니다.

다음 시간이 주어졌다고 하면 

빨간색 표시된 곳을 선택하면 서로 회의시간이 겹치지 않게 해서 총 4개의 회의를 진행 할 수 있습니다.

 

이를 통해 알 수 있는 사실은 회의가 끝나는 시간이 가장 이른것이 최적해라는 것을 알 수 있습니다.

이러한 구현방식은 Greedy 알고리즘을 통해 해결할 수 있습니다.

 

따라서 가장 먼저 회의가 끝나는시간을 기준으로 회의시작 시간이 기준 시간보다 먼저 시작하면 무시해주면 됩니다.

이러한 과정을 계속 해서 갱신해 나가면서 진행해주면 됩니다.

for (ll i = 0; i < n; i++) {
		cin >> a >> b;
		v.push_back({ a,b });
	}

벡터 v를 pair형으로 받았습니다. {회의 시작 시간, 회의 끝나는 시간}

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


bool cmpare(pair<ll, ll>x, pair<ll, ll>y) {
	if (x.second == y.second)
		return x.first < y.first;
	else return x.second < y.second;
}

끝나는 시간을 기준으로 오름차순으로 정렬해주었습니다.

또한 만약에 끝나는 시간이 서로 같다면 시작시간이 더 이른것이 먼저오게 정렬해주었습니다. 

for (ll i = 0; i < n; i++) {
	ll start = v[i].first;
	ll end = v[i].second;

	if (start >= ans) {
		cnt++;
		ans = end;
	}
}

cnt 변수는 가능한 회의를 세는 변수입니다.

ans를 계속 변경시켜주어서 서로 겹치지않게 갱신해줍니다.

---

전체 코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<pair<ll,ll>>v;
ll a, b;
bool cmpare(pair<ll, ll>x, pair<ll, ll>y);
ll ans, cnt;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> a >> b;
        v.push_back({ a,b });
    }
    sort(v.begin(), v.end(), cmpare);
    for (ll i = 0; i < n; i++) {
        ll start = v[i].first;
        ll end = v[i].second;
 
        if (start >= ans) {
            cnt++;
            ans = end;
        }
    }
    cout << cnt;
    return 0;
}
bool cmpare(pair<ll, ll>x, pair<ll, ll>y) {
    if (x.second == y.second)
        return x.first < y.first;
    else return x.second < y.second;
}