Tarche

movie-festival-2-sort-default

Jun 19th, 2021
1,359
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     ios_base::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     cout.tie(nullptr);
  9.  
  10.     int n, k;
  11.     cin >> n >> k;
  12.  
  13.     vector<pair<int, int>> movies(n);
  14.     for (int i = 0; i < n; i++)
  15.         cin >> movies[i].second >> movies[i].first;
  16.  
  17.     sort(movies.begin(), movies.end());
  18.  
  19.     multiset<int> endings;
  20.     for (int i = 0; i < k; i++)
  21.         endings.insert(0);
  22.  
  23.     int ans = 0;
  24.     for (int i = 0; i < n; i++) {
  25.         auto it = endings.upper_bound(movies[i].second);
  26.         if (it == endings.begin())
  27.             continue;
  28.         endings.erase(--it);
  29.         endings.insert(movies[i].first);
  30.         ans++;
  31.     }
  32.  
  33.     cout << ans << '\n';
  34. }
RAW Paste Data