STANAANDREY

non-overlappInts

Jul 28th, 2021 (edited)
532
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5.  
  6. class Solution
  7. {
  8.     static bool comp(vector<int>& v1, vector<int>& v2)
  9.     {
  10.         if (v1[1] == v2[1])
  11.             return v1[0] < v2[0];
  12.         return v1[1] < v2[1];
  13.     }
  14. public:
  15.     int eraseOverlapIntervals(vector<vector<int>>& intervals)
  16.     {
  17.         vector<vector<int>> r;
  18.         int sz = intervals.size();
  19.         sort(intervals.begin(), intervals.end(), comp);
  20.         auto aux = intervals[0];
  21.         int ans = 1;
  22.         for (int i = 1; i < intervals.size(); i++)
  23.         {
  24.             if (intervals[i][0] > aux[1])
  25.             {
  26.                 ans++;
  27.                 aux = intervals[i];
  28.             } else {
  29.                 intervals.erase(intervals.begin() + i);
  30.                 i--;
  31.             }
  32.         }
  33.         return sz - ans;
  34.     }
  35. };
  36.  
  37. signed main()
  38. {
  39.     int n;
  40.     cin >> n;
  41.     vector<vector<int>> segs(n, vector<int>(2));
  42.     for (auto &it : segs)
  43.     {
  44.         cin >> it[0] >> it[1];
  45.     }
  46.     Solution s;
  47.     int e = s.eraseOverlapIntervals(segs);
  48.     cout << "erased:" << e << endl;
  49.     for (const auto &it : segs)
  50.     {
  51.         cout << it[0] << ' ' << it[1] << endl;
  52.     }
  53.     return 0;
  54. }
  55.  
RAW Paste Data