Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- struct node{
- int number;
- int data;
- int start_time;
- int finish_time;
- };
- bool compareData( node a, node b ) {return a.data < b.data;}
- bool compareNum( node a, node b ) {return a.number < b.number;}
- void ActivitySelection(int n , int s[] , int f[]);
- vector<node> initialize(int n , int s[] , int f[]);
- vector<node> initial_setting(vector<node> vec , vector<node> collisions);
- void release(vector<node> &print , vector<node> collisions , bool ocupied[]);
- int main(){
- int n;
- cin >> n;
- int s[n], f[n];
- for(int i = 0 ; i < n ; i++){
- cin >> s[i];
- }
- for(int i = 0 ; i < n ; i++){
- cin >> f[i];
- }
- ActivitySelection(n,s,f);
- system("pause");
- return 0;
- }
- void ActivitySelection(int n , int s[] , int f[]){
- vector<node> vec = initialize(n ,s ,f);
- vector<node> collisions_temp;
- vector<node> collisions = initial_setting(vec , collisions_temp);
- int duration = *max_element(f,f+n) - *min_element(s,s+n);
- bool ocupied[duration];
- for(int i = 0 ; i < n ; i++){
- ocupied[i] = false;
- }
- vector<node> print;
- int count = 0;
- while(count < n){
- node temp_node = vec[count];
- bool flag = true ;
- for(int i = temp_node.start_time+1 ; i <= temp_node.finish_time ; i++){
- if(ocupied[i] == true){
- flag = false;
- }
- }
- if(flag == true){
- print.push_back(temp_node);
- for(int k = temp_node.start_time+1 ; k <= temp_node.finish_time ; k++){
- ocupied[k] = true;
- }
- }
- count++;
- }
- cout << print.size() << "\n" << "(";
- release(print , collisions , ocupied);
- sort(print.begin(),print.end(),compareNum);
- for ( int i = 0 ; i < n ; i ++ ) {
- cout << print[i].number << ",";
- }
- cout << ")" << endl;
- }
- vector<node> initialize(int n , int s[] , int f[]){
- vector<node> vec;
- for(int i = 0 ; i < n ; i++){
- node temp;
- temp.number = i+1;
- temp.data = f[i] - s[i];
- temp.start_time = s[i];
- temp.finish_time = f[i];
- vec[i] = temp;
- }
- sort(vec.begin(), vec.end(), compareData);
- return vec;
- }
- vector<node> initialetting(vector<node> vec , vector<node> collisions){
- for(int i = 0 ; i < vec.size() ; i++){
- node temp = vec[i];
- for(int j = 0 ; j < vec.size() ; j++){
- if(i == j){}
- else{
- node compare = vec[j];
- if(temp.start_time <= compare.start_time && temp.finish_time >= compare.finish_time){
- collisions.push_back(temp);
- collisions.push_back(compare);
- break;
- }
- }
- }
- }
- return collisions;
- }
- void release(vector<node> &print , vector<node> collisions , bool ocupied[]){
- for(int i = 0 ; i < print.size() ; i++){
- node temp = print[i];
- for(int j = 1 ; j < collisions.size() ; j+=2){
- node compare = collisions[j];
- if(compare.number == temp.number){
- node temp_node = collisions[j-1];
- bool flag = true ;
- vector<bool> temp_vec;
- for(int yo = temp_node.start_time ; yo <= temp_node.finish_time ; yo++){
- temp_vec.push_back(ocupied[yo]);
- }
- for(int yo = compare.start_time+1 ; yo <= compare.finish_time ; yo++){
- temp_vec[yo] = false;
- }
- for(int i = temp_node.start_time+1 ; i <= temp_node.finish_time ; i++){
- if(temp_vec[i] == true){
- flag = false;
- }
- }
- if(flag == true){
- print.push_back(temp_node);
- for(int k = temp_node.start_time+1 ; k <= temp_node.finish_time ; k++){
- ocupied[k] = true;
- }
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement