fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Activity Selection
  4. //
  5. //  Created by Himanshu on 16/08/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <algorithm>
  10. #include <vector>
  11. using namespace std;
  12. typedef struct node Node;
  13.  
  14. struct node {
  15.     int s, f;
  16.     int pos;
  17. };
  18.  
  19. bool cmp (const Node &a, const Node &b){
  20.     return a.f < b.f;
  21. }
  22.  
  23. vector<int> solve(vector<int> s, vector<int> f) {
  24.     vector<int> ans;
  25.     int N = (int)s.size(), j = 0;
  26.     Node p[N];
  27.  
  28.     for (int i=0; i<N; i++) {
  29.         p[i].s = s[i];
  30.         p[i].f = f[i];
  31.         p[i].pos = i;
  32.     }
  33.  
  34.     sort(p, p+N, &cmp);
  35.     ans.push_back(p[0].pos);
  36.  
  37.     for (int i=1; i<N; i++) {
  38.         if (p[i].s >= p[j].f) {
  39.             ans.push_back(p[i].pos);
  40.             j = i;
  41.         }
  42.     }
  43.     return ans;
  44. }
  45.  
  46. int main() {
  47.     vector<int> start = {1, 3, 0, 5, 8, 5};
  48.     vector<int> finish = {2, 4, 6, 7, 9, 9};
  49.     vector<int> selectedActivities = solve(start, finish);
  50.  
  51.     cout<<"Selected activities: \n";
  52.     for (int i=0; i<selectedActivities.size(); i++) {
  53.         cout<<selectedActivities[i]<<" ";
  54.     }
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 5604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Selected activities: 
0 1 3 4
https://ideone.com/75VzHD
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!