1931번: 회의실 배정(30분)

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

구현 아이디어 5분 구현 25분

풀이

1. 정렬
   • 이 문제는 시작시간만 기준이 되면 안됨. 종료시간도 정렬의 기준에 포함되어야 함.

2. 시작하자마자 끝나는 회의
   • 얘네들은 여러개 나와도 다 카운트.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Meeting
{
    int StartMeetingSec;
    int EndMeetingSec;
    Meeting(int StartMeetingSec, int EndMeetingSec)
    {
        this->StartMeetingSec = StartMeetingSec;
        this->EndMeetingSec = EndMeetingSec;
    }
    bool operator<(const Meeting& Meeting)
    {
        if(StartMeetingSec != Meeting.StartMeetingSec) return StartMeetingSec < Meeting.StartMeetingSec;
        if (EndMeetingSec != Meeting.EndMeetingSec) return EndMeetingSec < Meeting.EndMeetingSec;
        return false;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "rt", stdin);

    vector<Meeting> VecMeetings;

    int N{};
    cin >> N;

    int StartMeetingSec{}, EndMeetingSec{};

    for (int i = 0; i < N; ++i)
    {
        cin >> StartMeetingSec >> EndMeetingSec;
        VecMeetings.push_back(Meeting(StartMeetingSec, EndMeetingSec));
    }

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

    int NumMeeting{ 1 };
    Meeting CurrentMeeting(VecMeetings[0]);

    for (int i = 1; i < VecMeetings.size(); ++i)
    {
        Meeting NextMeeting = VecMeetings[i];
        if (NextMeeting.StartMeetingSec >= CurrentMeeting.EndMeetingSec)
        {
            CurrentMeeting = NextMeeting;
            ++NumMeeting;
        }
        else
        {
            CurrentMeeting.EndMeetingSec = min(CurrentMeeting.EndMeetingSec, NextMeeting.EndMeetingSec);
        }
    }

    cout << NumMeeting;

    return 0;
}