[Gold V] 회의실 배정 - 1931

문제 링크

성능 요약

메모리: 2800 KB, 시간: 20 ms

분류

그리디 알고리즘, 정렬

제출 일자

2025년 11월 16일 00:29:22

문제 설명

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

입력

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

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

첫번째 코드

// 백준 1931

// - 아이디어
//      끝나는 시간을 기준으로 정렬한다. (stl::sort)
//      끝나는 시간이 같은 회의들 중에서 시작 시간이 짧은 회의를 확정한다.
//      -> 일종의 그리디 알고리즘
// 
// - 복잡도
//      입력 및 삽입 = O(n)
//      정렬 = O(nlogn)
//      그리디 = O(n)
//      -> O(nlogn) , N= 10^5 ,가능
// 
//  - 자료구조
//      배열: pair<start,end>[][]

#include <iostream>
#include <algorithm>
#define MAX_LEN 100'000

//struct Time { int start; int end; };
std::pair<int,int> timeBoard[MAX_LEN];

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    int N;

    std::cin >> N;

    for (int i = 0; i < N; i++) {
        std::pair<int, int> time;
        std::cin >> time.second >> time.first;
        timeBoard[i] = time;
    }

    std::sort(timeBoard, timeBoard + N);

    int selectEnd = timeBoard[0].first;
    int prevEnd = timeBoard[0].first;
    int prevStart = timeBoard[0].second;
    int count = 1;
    for (int i = 1; i < N; i++) {
        int end = timeBoard[i].first;
        int start = timeBoard[i].second;

        if (end != prevEnd) {
            if (start >= selectEnd) {
                count++;
                selectEnd = end;
            }
            prevEnd = end;
            continue;
        }
        else {
            if (start >= selectEnd) {
                count++;
                selectEnd = end;
            }
        }
    }
    std::cout << count;
    return 0;
}

보완

sort까진 좋았는데, 초이스하는 과정이 비효율적이였다.

for문에서 end, prevEnd를 비교하여 분기를 나눠주었는데, 이전 선택된 end와 현재 end가 같던 안같던, 현재의 start시간과 그대로 비교해주면 특수한 케이스를 포함한 모든 경우도 통과된다.

분기 내부에서 애초에 같은 로직을 수행하고 있다.. count++

그리고 사용하지않는 변수도 정리하였다.

제출 코드

// 백준 1931

// - 아이디어
//      끝나는 시간을 기준으로 정렬한다. (stl::sort)
//      끝나는 시간이 같은 회의들 중에서 시작 시간이 짧은 회의를 확정한다.
//      -> 일종의 그리디 알고리즘
// 
// - 복잡도
//      입력 및 삽입 = O(n)
//      정렬 = O(nlogn)
//      그리디 = O(n)
//      -> O(nlogn) , N= 10^5 ,가능
// 
//  - 자료구조
//      배열: pair<start,end>[][]

#include <iostream>
#include <algorithm>
#define MAX_LEN 100'000

//struct Time { int start; int end; };
std::pair<int,int> timeBoard[MAX_LEN];

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    int N;

    std::cin >> N;

    for (int i = 0; i < N; i++) {
        std::pair<int, int> time;
        std::cin >> time.second >> time.first;
        timeBoard[i] = time;
    }

    std::sort(timeBoard, timeBoard + N);

    int currEnd = 0;
    int answer = 0;
    for (int i = 0; i < N; i++) {
        int end = timeBoard[i].first;
        int start = timeBoard[i].second;

        if (start >= currEnd) {
            answer++;
            currEnd = end;
        }
        continue;
    }
    std::cout << answer;
    return 0;
}