백준 1931번 회의실배정

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

탐욕법(greedy method)을 이용하여 푸는 문제였습니다.

/*

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다.

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

회의의 시작시간과 끝나는 시간이 같을 수도 있다.

이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

*/

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N; //<=100000

int cBegin[100000], cEnd[100000]; //conference 시작시간, 끝나는 시간

 

//탐욕법을 사용

//제일 먼저 시작하는 회의를 선택하고 그와 겹치는 회의들 제외

//첫번째 회의가 끝나고 제일 빨리 시작하는 다음 회의를 선택하고 겹치는 회의들 제외

int schedule(void)

{

        //일찍 끝나는 순서대로 정렬

        vector<pair<int, int>> order;

        for (int i = 0; i < N; i++)

               order.push_back(make_pair(cEnd[i], cBegin[i]));

        sort(order.begin(), order.end());

        //earliest: 다음 회의가 시작할 수 있는 가장 빠른 시간

        //selected: 지금까지 선택한 회의의 수

        int earliest = 0, selected = 0;

        for (int i = 0; i < order.size(); i++)

        {

               int meetingBegin = order[i].second, meetingEnd = order[i].first;

               if (earliest <= meetingBegin)

               {

                       //earliest를 마지막 회의가 끝난 시간 이후로 갱신

                       earliest = meetingEnd;

                       selected++;

               }

        }

        return selected;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

               cin >> cBegin[i] >> cEnd[i];

 

        cout << schedule() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략