Untitled
unknown
c_cpp
a year ago
1.2 kB
2
Indexable
Never
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Executive { int startHouse; int endHouse; }; bool compareExecutives(Executive a, Executive b) { return a.startHouse < b.startHouse; } int nonOverlappingExecutives(vector<Executive>& execs) { if (execs.size() == 0) return 0; // Sort the executives based on startHouse sort(execs.begin(), execs.end(), compareExecutives); int count = 1; // Count of non-overlapping routes int end = execs[0].endHouse; for (int i = 1; i < execs.size(); i++) { // If current executive's start is greater than previous end, they don't overlap if (execs[i].startHouse > end) { count++; end = execs[i].endHouse; } else { // Otherwise, update the end with the maximum endHouse end = max(end, execs[i].endHouse); } } return count; } int main() { int N, M; cin >> N >> M; vector<Executive> execs(N); for (int i = 0; i < N; i++) { cin >> execs[i].startHouse >> execs[i].endHouse; } cout << nonOverlappingExecutives(execs) << endl; return 0; }