Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
Tags
more
Archives
Today
Total
관리 메뉴

Mini

[알고리즘] 백준 1931 회의실 배정 // 그리디, 라인스위핑, 정렬 본문

Algorithm/greedy

[알고리즘] 백준 1931 회의실 배정 // 그리디, 라인스위핑, 정렬

Mini_96 2025. 1. 28. 23:08

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

* 풀이

  • start로 정렬? -> 반례 -> 우디르
  • end? -> 되네

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

int n,ret;
vector<pair<int,int>> v; // < 끝시, 시작시 >

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

   cin>>n;
   for (int i=0;i<n;++i) {
      int a,b;
      cin>>a>>b;
      v.push_back({b,a});
   }
   sort(v.begin(),v.end());

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