JArchive 프로그래밍 일기

강의실 배정 문제 링크 

리뷰 

'많은'강의를 배정하려면,  강의가 빨리 끝나야 한다. 

따라서 처음에 강의의 종료 시점을 기준으로 오름차순 정렬한다. 

첫 강의의 종료 시점을 cur 에 저장하고, cur보다 크거나 같은 시점에서 시작하는 강의를 배정한다. 

강의를 배정하면 cur가 해당 강의의 종료 시점으로 갱신되야 한다. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

int n, s, f, cnt;
vector<pair<int,int>> v;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> s >> f;
    v.push_back({f, s}); // 종료가 빠른 수업 먼저.
  }

  sort(v.begin(), v.end());
  int cur = v[0].first; // 첫 종료지점
  cnt = 1; // 강의 개수 

  for(int i = 1 ; i < n; i++){
    if(cur <= v[i].second){
      cur = v[i].first;
      cnt++;
    }
  }
  cout << cnt;
  return 0;
}

제출 기록