fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool compare(const vector<int>& a, const vector<int>& b) {
  5.     return a[1] < b[1];
  6. }
  7.  
  8. int activitySelection(vector<int> &start, vector<int> &finish) {
  9.     vector<vector<int>> arr;
  10.  
  11.     for (int i = 0; i < start.size(); i++) {
  12.         arr.push_back({start[i], finish[i]});
  13.     }
  14.  
  15.     // Sort activities by finish time
  16.     sort(arr.begin(), arr.end(), compare);
  17.  
  18.     // At least one activity can be performed
  19.     int count = 1;
  20.  
  21.     // Index of last selected activity
  22.     int j = 0;
  23.  
  24.     for (int i = 1; i < arr.size(); i++) {
  25.  
  26.         // Check if current activity starts
  27.         // after last selected activity finishes
  28.         if (arr[i][0] > arr[j][1]) {
  29.             count++;
  30.  
  31.             // Update last selected activity
  32.             j = i;
  33.         }
  34.     }
  35.  
  36.     return count;
  37. }
  38.  
  39. int main() {
  40.     vector<int> start = {1, 3, 0, 5, 8, 5};
  41.     vector<int> finish = {2, 4, 6, 7, 9, 9};
  42.     cout << activitySelection(start, finish);
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/mooY5e
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

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!