fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Delivery {
  4.     public:
  5.     int driverId;
  6.     int64_t startTime;
  7.     int64_t endTime;
  8.     int64_t costHundredthCents;
  9.     bool paid = false;
  10. };
  11. class ConcurrentDeliveryDTO{
  12.     public :
  13.     int64_t time;
  14.     int driverId;
  15.     int type;
  16. };
  17.  
  18. class DeliveryCostManager3 {
  19. private:
  20.     unordered_map<int, int64_t> driverRates; // driverId → hundredths of a cent/hour
  21.     vector<Delivery> deliveries;             // sorted by endTime
  22.  
  23.     int64_t globalTotalCost = 0;
  24.     int64_t globalPaidCost = 0;
  25.  
  26. public:
  27.  
  28.     void addDriver(int driverId, double usdHourlyRate) {
  29.         // Store as hundredths of a cent/hour
  30.         int64_t rateHundredthCentsPerHour = (int64_t)(llround(usdHourlyRate * 10000));
  31.         driverRates[driverId] = rateHundredthCentsPerHour;
  32.     }
  33.  
  34.     void recordDelivery(int driverId, int64_t startTime, int64_t endTime) {
  35.         if (endTime - startTime > 3 * 3600)
  36.             throw invalid_argument("Delivery exceeds 3-hour limit");
  37.  
  38.         int64_t rate = driverRates[driverId];
  39.         int64_t durationSecs = endTime - startTime;
  40.         int64_t cost = (rate * durationSecs) / 3600;
  41.  
  42.         deliveries.push_back({driverId, startTime, endTime, cost, false});
  43.         globalTotalCost += cost;
  44.     }
  45.  
  46.     void payUpTo(int64_t payTime) {
  47.         for (auto d : deliveries) {
  48.             if (!d.paid && d.endTime <= payTime) {
  49.                 d.paid = true;
  50.                 globalPaidCost += d.costHundredthCents;
  51.             }
  52.         }
  53.     }
  54.  
  55.     double getTotalCost() { return (double)(globalTotalCost) / 10000.0; }
  56.     double getTotalCostPaid()  { return (double)(globalPaidCost) / 10000.0; }
  57.     double getTotalCostUnpaid()  {
  58.         return (double)(globalTotalCost - globalPaidCost) / 10000.0;
  59.     }
  60.  
  61. bool static compareDeliveries(ConcurrentDeliveryDTO &a,ConcurrentDeliveryDTO &b){
  62.     return a.time<b.time;
  63. }
  64.  
  65. int maxDriverrs(int64_t endTime) {
  66.     int64_t startTime  = endTime - (24*60*60);
  67.     vector<ConcurrentDeliveryDTO> validDeliveries;
  68.     for(auto d : deliveries){
  69.         if(d.endTime<startTime){
  70.             continue;
  71.         }
  72.         if(d.startTime>endTime){
  73.             continue;
  74.         }
  75.         validDeliveries.push_back({max(startTime,d.startTime),d.driverId,0});
  76.         validDeliveries.push_back({min(endTime,d.endTime),d.driverId,1});
  77.     }
  78.     sort(validDeliveries.begin(),validDeliveries.end(),compareDeliveries);
  79.     unordered_map<int,int> countDelivery;
  80.     int currentDrivers = 0;
  81.     int maxDrivers  = 0 ;
  82.     for(auto it: validDeliveries){
  83.         if(it.type==0){
  84.             countDelivery[it.driverId]++;
  85.         }
  86.         if(it.type==1){
  87.             countDelivery[it.driverId]--;
  88.             if(countDelivery[it.driverId]==0){
  89.                 countDelivery.erase(it.driverId);
  90.             }
  91.         }
  92.         currentDrivers = countDelivery.size();
  93.         maxDrivers = max(maxDrivers,currentDrivers);
  94.     }
  95.     return maxDrivers;
  96. }
  97. };
  98.  
  99.  
  100. int main(){
  101.     DeliveryCostManager3 manager;
  102.  
  103.     manager.addDriver(1, 35.10);
  104.     manager.addDriver(2, 15.15);
  105.     manager.addDriver(3, 8.55);
  106.     manager.addDriver(4, 11.28);
  107.     manager.addDriver(5, 0.1);
  108.     manager.recordDelivery(1, 0, 3600);
  109.     manager.recordDelivery(5, 0, 3600);
  110.     manager.recordDelivery(2, 0, 5400);
  111.     manager.recordDelivery(2, 4400, 6200);
  112.     manager.recordDelivery(5, 3600, 7200);
  113.     manager.recordDelivery(5,7200, 10800);
  114.     manager.recordDelivery(5, 10800, 14400);
  115.     manager.recordDelivery(5, 14400, 18000);
  116.  
  117.     cout << fixed << setprecision(2);
  118.     // cout << "Driver 1 total: $" << manager.getDriverTotalCost(1) << std::endl;
  119.     // cout << "Driver 2 total: $" << manager.getDriverTotalCost(2) << std::endl;
  120.     cout << "Global total:   $" << manager.getTotalCost() << std::endl;
  121.  
  122.     // cout<<manager.maxSimultaneousDrivers24HourBefore(18000)<<endl;
  123.     cout<<manager.maxDriverrs(18000)<<endl;
  124.     return 0;
  125. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Global total:   $65.90
3
https://ideone.com/ylDYK7
language:
C++14 (gcc 8.3)
created:
13 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!