N meeting in a room # Greedy Algorithm

#include <bits/stdc++.h>
using namespace std;
// SC = o(n) TC = O(n + nlogn)

int maxMeetings(int start[], int end[], int n)
    {
        // Your code 
        vector<pair<int,int>> slots;
        for(int i=0;i<n;i++){
            slots.push_back({end[i], start[i]});
        }

        sort(slots.begin(), slots.end());

        int ans = 1;
        int c = slots[0].first;

        for(int i=1;i<n;i++){
            if(slots[i].second > c){
                ans++;
                c = slots[i].first;
             }
        }

        return ans;
    }

int main(){
    int n;
    cin >> n;

    int start[n];
    int end[n];

    for(int i=0;i<n;i++){
        cin >> start[i];
    }
    for(int i=0;i<n;i++){
        cin >> end[i];
    }

    cout << maxMeetings(start, end, n);

    return 0;
}



Comments

Popular Posts