Given two arrays S[] and E[] of size N denoting starting and closing time of the shops and an integer value K denoting the number of people, the task is to find out the maximum number of shops they can visit in total if they visit each shop optimally based on the following conditions:
A shop can be visited by only one person A person cannot visit another shop if its timing collide with it Examples:
Input: S[] = {1, 8, 3, 2, 6}, E[] = {5, 10, 6, 5, 9}, K = 2 Output: 4 Explanation: One possible solution can be that first person visits the 1st and 5th shops meanwhile second person will visit 4th and 2nd shops.
Input: S[] = {1, 2, 3}, E[] = {3, 4, 5}, K = 2 Output: 3 Explanation: One possible solution can be that first person visits the 1st and 3rd shops meanwhile second person will visit 2nd shop.
My solution approach code -->
bool mycomp(const pair<int, int> &p1, const pair<int, int> &p2){
if(p1.second == p2.second){
return p1.first > p2.first;
}
return p1.second < p2.second;
}
int maximumActivities_1_person(vector<pair<int, int>> &v, int &totalRemaining, VI &visited){
int ans=0, n=v.size(), last_end = -1;
for(int i=0;i<n;i++){
if((last_end == -1 || (last_end != -1 && v[i].first >= last_end)) && visited[i] == 0) ans++, last_end = v[i].second, totalRemaining--, visited[i]=1;
}
return ans;
}
int maximumActivities_K_persons(VI &start, VI &end, int K){
int n = start.size();
vector<pair<int, int>> v;
for(int i=0;i<n;i++){
v.push_back({start[i], end[i]});
}
sort(v.begin(), v.end(), mycomp);
int totalRemaining = n;
VI visited(n, 0);
int no_of_workers = K;
int ans=0;
while(totalRemaining && no_of_workers){
no_of_workers--;
int c = maximumActivities_1_person(v, totalRemaining, visited);
cout<<c<<endl;
ans+=c;
}
return ans;
}
void solve(){
int n, K;cin>>n>>K;
VI start(n, 0), end(n, 0);
for(int i=0;i<n;i++){
cin>>start[i]>>end[i];
}
cout<<maximumActivities_K_persons(start, end, K)<<endl;
}
Is my algorithm correct?
There is no online judge on which this problem is present so I cannot test against the test cases. So if anyone can validate if the algorithm devised by me is correct.
