Tarche

movie-festival-2-sort-lambda

Jun 19th, 2021
1,120
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.         [](const pair<int, int>& a, const pair<int, int>& b) -> bool {
  19.             return (a.first < b.first) ? true : (a.second < b.second);
  20.         });
  21.  
  22.     multiset<int> endings;
  23.     for (int i = 0; i < k; i++)
  24.         endings.insert(0);
  25.  
  26.     int ans = 0;
  27.     for (int i = 0; i < n; i++) {
  28.         auto it = endings.upper_bound(movies[i].second);
  29.         if (it == endings.begin())
  30.             continue;
  31.         endings.erase(--it);
  32.         endings.insert(movies[i].first);
  33.         ans++;
  34.     }
  35.  
  36.     cout << ans << '\n';
  37. }
RAW Paste Data