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
Post a Comment