Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define fi first
- #define se second
- class Solution
- {
- static bool comp(vector<int>& v1, vector<int>& v2)
- {
- if (v1[1] == v2[1])
- return v1[0] < v2[0];
- return v1[1] < v2[1];
- }
- public:
- int eraseOverlapIntervals(vector<vector<int>>& intervals)
- {
- vector<vector<int>> r;
- int sz = intervals.size();
- sort(intervals.begin(), intervals.end(), comp);
- auto aux = intervals[0];
- int ans = 1;
- for (int i = 1; i < intervals.size(); i++)
- {
- if (intervals[i][0] > aux[1])
- {
- ans++;
- aux = intervals[i];
- } else {
- intervals.erase(intervals.begin() + i);
- i--;
- }
- }
- return sz - ans;
- }
- };
- signed main()
- {
- int n;
- cin >> n;
- vector<vector<int>> segs(n, vector<int>(2));
- for (auto &it : segs)
- {
- cin >> it[0] >> it[1];
- }
- Solution s;
- int e = s.eraseOverlapIntervals(segs);
- cout << "erased:" << e << endl;
- for (const auto &it : segs)
- {
- cout << it[0] << ' ' << it[1] << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement