[백준 C++] 1931 회의실 배정 - 그리디

1931번: 회의실 배정

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Meet
{
‌int Start;
‌int End;

‌Meet(int StartTime, int EndTime) : Start(StartTime), End(EndTime) {}

‌bool operator<(const Meet& rhs) const
‌{
‌‌return (End != rhs.End) ? End < rhs.End : Start < rhs.Start;
‌}
};

vector<Meet> Meets;

int main()
{
‌int n;
‌cin >> n;
‌Meets.reserve(n);

‌for (int i = 0; i < n; ++i)
‌{
‌‌int Start = 0, End = 0;
‌‌cin >> Start >> End;
‌‌Meets.emplace_back(Meet(Start, End));
‌}

‌sort(Meets.begin(), Meets.end(), less<>());

‌int Count = 1;
‌int PrevEndTime = Meets.front().End;
‌for (int i = 1; i < n; ++i)
‌{
‌‌if (PrevEndTime <= Meets[i].Start)
‌‌{
‌‌‌PrevEndTime = Meets[i].End;
‌‌‌++Count;
‌‌}
‌}

‌cout << Count;
}

---

 

최대한 많은 수의 회의를 배정해야 하므로

회의가 끝나는 시간을 기준으로 오름차순 정렬하는 것이 중요 포인트였습니다.

 

따로 구조체를 만들어서 연산자 오버로딩을 통해 정렬하도록 풀었습니다.