Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. struct node{
  7.  
  8. int number;
  9. int data;
  10. int start_time;
  11. int finish_time;
  12. };
  13.  
  14. bool compareData( node a, node b ) {return a.data < b.data;}
  15. bool compareNum( node a, node b ) {return a.number < b.number;}
  16. void ActivitySelection(int n , int s[] , int f[]);
  17. vector<node> initialize(int n , int s[] , int f[]);
  18. vector<node> initial_setting(vector<node> vec , vector<node> collisions);
  19. void release(vector<node> &print , vector<node> collisions , bool ocupied[]);
  20.  
  21. int main(){
  22. int n;
  23. cin >> n;
  24. int s[n], f[n];
  25. for(int i = 0 ; i < n ; i++){
  26. cin >> s[i];
  27. }
  28. for(int i = 0 ; i < n ; i++){
  29. cin >> f[i];
  30. }
  31. ActivitySelection(n,s,f);
  32.  
  33. system("pause");
  34. return 0;
  35. }
  36.  
  37. void ActivitySelection(int n , int s[] , int f[]){
  38. vector<node> vec = initialize(n ,s ,f);
  39. vector<node> collisions_temp;
  40. vector<node> collisions = initial_setting(vec , collisions_temp);
  41.  
  42. int duration = *max_element(f,f+n) - *min_element(s,s+n);
  43. bool ocupied[duration];
  44. for(int i = 0 ; i < n ; i++){
  45. ocupied[i] = false;
  46. }
  47.  
  48. vector<node> print;
  49. int count = 0;
  50. while(count < n){
  51. node temp_node = vec[count];
  52. bool flag = true ;
  53. for(int i = temp_node.start_time+1 ; i <= temp_node.finish_time ; i++){
  54. if(ocupied[i] == true){
  55. flag = false;
  56. }
  57. }
  58. if(flag == true){
  59. print.push_back(temp_node);
  60. for(int k = temp_node.start_time+1 ; k <= temp_node.finish_time ; k++){
  61. ocupied[k] = true;
  62. }
  63. }
  64. count++;
  65. }
  66.  
  67.  
  68. cout << print.size() << "\n" << "(";
  69.  
  70. release(print , collisions , ocupied);
  71. sort(print.begin(),print.end(),compareNum);
  72. for ( int i = 0 ; i < n ; i ++ ) {
  73. cout << print[i].number << ",";
  74. }
  75. cout << ")" << endl;
  76. }
  77.  
  78. vector<node> initialize(int n , int s[] , int f[]){
  79. vector<node> vec;
  80. for(int i = 0 ; i < n ; i++){
  81. node temp;
  82. temp.number = i+1;
  83. temp.data = f[i] - s[i];
  84. temp.start_time = s[i];
  85. temp.finish_time = f[i];
  86. vec[i] = temp;
  87. }
  88. sort(vec.begin(), vec.end(), compareData);
  89. return vec;
  90. }
  91.  
  92. vector<node> initialetting(vector<node> vec , vector<node> collisions){
  93. for(int i = 0 ; i < vec.size() ; i++){
  94. node temp = vec[i];
  95. for(int j = 0 ; j < vec.size() ; j++){
  96. if(i == j){}
  97. else{
  98. node compare = vec[j];
  99. if(temp.start_time <= compare.start_time && temp.finish_time >= compare.finish_time){
  100. collisions.push_back(temp);
  101. collisions.push_back(compare);
  102. break;
  103. }
  104. }
  105. }
  106. }
  107. return collisions;
  108. }
  109.  
  110. void release(vector<node> &print , vector<node> collisions , bool ocupied[]){
  111. for(int i = 0 ; i < print.size() ; i++){
  112. node temp = print[i];
  113. for(int j = 1 ; j < collisions.size() ; j+=2){
  114. node compare = collisions[j];
  115. if(compare.number == temp.number){
  116. node temp_node = collisions[j-1];
  117. bool flag = true ;
  118. vector<bool> temp_vec;
  119. for(int yo = temp_node.start_time ; yo <= temp_node.finish_time ; yo++){
  120. temp_vec.push_back(ocupied[yo]);
  121. }
  122. for(int yo = compare.start_time+1 ; yo <= compare.finish_time ; yo++){
  123. temp_vec[yo] = false;
  124. }
  125. for(int i = temp_node.start_time+1 ; i <= temp_node.finish_time ; i++){
  126. if(temp_vec[i] == true){
  127. flag = false;
  128. }
  129. }
  130. if(flag == true){
  131. print.push_back(temp_node);
  132. for(int k = temp_node.start_time+1 ; k <= temp_node.finish_time ; k++){
  133. ocupied[k] = true;
  134. }
  135. }
  136. }
  137. }
  138. }
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement