Niloy007

In Class Assignment On Greedy 2

May 8th, 2021
506
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main () {
  5.     double arrival[] = {2.00, 2.10, 3.00, 3.20, 3.50, 5.00};
  6.     double departure[] = {2.30, 3.20, 3.40, 4.00, 4.30, 5.20};
  7.  
  8.     // double arrival[] = {9.00, 9.40, 9.50, 11.00, 15.00, 18.00};
  9.     // double departure[] = {9.10, 12.00, 11.20, 11.30, 19.00, 20.00};
  10.  
  11.     int a = sizeof(arrival) / sizeof(arrival[0]);
  12.     int d = sizeof(departure) / sizeof(departure[0]);
  13.  
  14.     sort(arrival, arrival + a);
  15.     sort(departure, departure + d);
  16.  
  17.     vector<pair<double, char>> merged;
  18.     int j = 0, k = 0;
  19.    
  20.     for (int i = 0; i < a + d; i++) {
  21.         if (arrival[j] <= departure[k] && j < a) {
  22.             merged.push_back({arrival[j], 'a'});
  23.             j++;
  24.         } else if (k < d) {
  25.             merged.push_back({departure[k], 'd'});
  26.             k++;
  27.         }
  28.     }
  29.  
  30.     // for (auto i : merged) {
  31.     //  cout << setprecision(2) << fixed << i.first << " " << i.second << endl;
  32.     // }
  33.     // cout << endl;
  34.  
  35.     pair<double, int> cnt;
  36.     cnt.second = 0;
  37.     int ans = -1;
  38.     for (auto i : merged) {
  39.         if (i.second == 'a') {
  40.             cnt.first = i.first;
  41.             cnt.second++;
  42.         } else if (i.second == 'd') {
  43.             cnt.second--;
  44.         }
  45.         ans = max(cnt.second, ans);
  46.         if (cnt.first == i.first && i.second == 'd') {
  47.             ans = cnt.second;
  48.         }
  49.     }
  50.     cout << ans << endl;
  51. }
  52.  
  53.  
RAW Paste Data