[소프티어] 강의실배정 (C++)

👓 문제 설명

---

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다.

---

💣 제한 사항

• 1 ≤ N ≤ 106 인 정수
  

• 1 ≤ Si ＜ Fi ≤ 10

---

🚨 접근 방법

문제를 잘 이해하면 금방 풀 수 있다.
최대한 많은 강의를 배치하려면 결국 종료시간이 빠른 순서대로 정렬만 하면 된다.

---

🚈 풀이

#include<iostream>
#include<vector>
#include<algorithm>
#define pp pair<int,int>
using namespace std;

int main(int argc, char** argv)
{
  // 시작시간과 종료시간이 주어졌을 때, 
  // 종료시간이 빠른 순서부터 정렬
  // 다음 원소의 시작시간이 이전 종료 시간과 같거나 큰 경우 강의 수를 추가하면서 탐색한다.
  vector<pp>classes;
  int n,s,f,answer=1;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>s>>f;
    classes.push_back(make_pair(f,s));
  }
  sort(classes.begin(),classes.end());
  int cur_end=classes[0].first;
  for(auto p:classes){
    if(cur_end<=p.second){
      answer++;
      cur_end=p.first;
    }
  }
  cout<<answer;
   return 0;
}