백준 1931 - 회의실 배정(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

그리디 알고리즘을 이용해 정렬로 푸는 문제입니다.

최대로 많은 회의를 찾는 문제입니다.

찾는 방법은 A라는 회의가 끝났을 때, A 회의 끝나는 시간에 가장 빨리 시작하는 회의면서 가장 빨리 끝나는 회의여야합니다.

따라서 먼저 끝나는 시간을 기준으로 오름차순으로 정렬합니다.

이때 끝나는 시간이 같다면 -> 일찍 시작하는 것을 선택해야합니다. 따라서 시작 시간을 기준으로 오름차순 정렬합니다.

 

가장 먼저 시작하는 회의는 첫번째에 있는 회의입니다.

따라서 해당 회의의 끝나는 시간을 시작으로 다음 회의를 계속 찾아주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

int N, ans = 1, last_time;
pair<int, int> room[100001];

bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second < b.second) return true;
    else if (a.second == b.second) {
        if (a.first < b.first) return true;
        else return false;
    }
    else return false;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> room[i].first >> room[i].second;
    sort(room, room + N, cmp);
    last_time = room[0].second;
    for (int i = 1; i < N; i++) {
        if (last_time <= room[i].first) {
            last_time = room[i].second;
            ans++;
        }
    }
    cout << ans;
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요