Advertisement
Guest User

Untitled

a guest
Dec 9th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct Node {
  6. int time;
  7. bool isBegin;
  8. };
  9.  
  10. void swap(Node *a, Node *b){
  11. Node temp = *a;
  12. *a = *b;
  13. *b = temp;
  14. }
  15.  
  16. bool compare(Node *a, Node *b){
  17. if (a->time < b->time) {
  18. return true;
  19. }
  20. else if (a->time == b->time) {
  21. if (a->isBegin == false) {
  22. return true;
  23. }
  24. else {
  25. return false;
  26. }
  27. }
  28. else {
  29. return false;
  30. }
  31. }
  32.  
  33. void siftDown(Node *beg, int size, int i){
  34. int left = 2 * i + 1;
  35. int right = 2 * i + 2;
  36. int max = i;
  37. if (left < size && compare(beg + i, beg + left)){
  38. max = left;
  39. }
  40. if (right < size && compare(beg + max, beg + right)){
  41. max = right;
  42. }
  43. if (max != i){
  44. swap(beg + i, beg + max);
  45. siftDown(beg, size, max);
  46. }
  47. }
  48.  
  49. void buildHeap(Node *beg, int size){
  50. for (int i = size / 2 - 1; i >= 0; --i){
  51. siftDown(beg, size, i);
  52. }
  53. }
  54.  
  55. void heapSort(Node *beg, Node *end){
  56. int size = end - beg + 1;
  57. buildHeap(beg, size);
  58. for (int i = size - 1; i >= 0; --i){
  59. swap(beg, beg + i);
  60. siftDown(beg, i, 0);
  61. }
  62. }
  63.  
  64.  
  65. int main(){
  66. int n;
  67. cin >> n;
  68.  
  69. Node* arr = new Node[2 * n];
  70.  
  71. for (int i = 0; i < n; i++) {
  72. cin >> arr[2 * i].time >> arr[2 * i + 1].time;
  73. arr[2 * i + 1].time += arr[2 * i].time;
  74. arr[2 * i].isBegin = true;
  75. arr[2 * i + 1].isBegin = false;
  76. }
  77.  
  78. heapSort(arr, arr + 2 * n - 1);
  79.  
  80. int answer = 0;
  81. int currAnswer = 0;
  82.  
  83. for (int i = 0; i < 2 * n; ++i) {
  84. if (arr[i].isBegin == true) {
  85. currAnswer++;
  86. }
  87. else {
  88. currAnswer--;
  89. }
  90.  
  91. if (currAnswer > answer) {
  92. answer = currAnswer;
  93. }
  94. }
  95.  
  96. cout << answer;
  97.  
  98. delete[] arr;
  99.  
  100. return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement