Untitled

mail@pastecode.io avatar
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;
}