[BOJ] 1931번 회의실 배정

BOJ 1931번 회의실 배정

그리디 나랑 안맞아

풀이

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

class Meeting {
  public:
  Meeting() {}
  Meeting(int start, int end) {
    this -> start = start;
    this -> end = end;
  }

  int start;
  int end;
};

int compare(Meeting a, Meeting b) {
  if(a.end == b.end) {
    return a.start < b.start;
  }
  return a.end < b.end;
}

int main() {
  int N, s, e;
  cin>>N;
  vector<Meeting> room(N);

  for(int i=0;i<N;i++){
    cin >> s >> e;
    room[i] = Meeting(s, e);
  }
  
  sort(room.begin(), room.end(), compare);

  int offset = 0, answer = 0;

  for(int i=0;i<N;i++){
    if(offset <= room[i].start){
      offset = room[i].end;
      answer++;
    }
  }

  cout << answer;
  
  return 0;
}

시간복잡도

sort() 함수의 경우 quick sort를 변형한 함수이기 때문에 최악의 경우 O(NlogN)을 보장한다.
정렬 후 for문까지 O(NlogN) + O(N) 이므로 시간복잡도는 O(NlogN)

다른 풀이

클래스를 사용하지 않고 pair나 구조체를 사용하면 아마 더 빠를 것