fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // part of question
  5. class Booking {
  6.     public : 
  7.         int bookingId;
  8.         int start;
  9.         int end;
  10.  
  11.         Booking(int id, int s, int e){
  12.             bookingId = id;
  13.             start = s;
  14.             end = e;
  15.         }
  16. };
  17.  
  18. // part of question
  19. class Court {
  20.     public:
  21.         int courtId;
  22.         vector<int> bookingIds;
  23.  
  24.         Court(int courtId,  vector<int> bookingIds) {
  25.             this->courtId = courtId;
  26.             this->bookingIds = bookingIds;
  27.         }
  28. };
  29.  
  30. // our logic
  31. class Event {
  32.     public : 
  33.         int time;
  34.         int bookingId;
  35.         string eventType;   // either start or end
  36.  
  37.         Event(int time, int bookingId, string eventType) {
  38.             this->time = time;
  39.             this->bookingId = bookingId;
  40.             this->eventType = eventType;
  41.         }
  42. };
  43.  
  44. struct myCmp {
  45.     bool operator()(Event a, Event b) {
  46.         if (a.time == b.time) {
  47.             return a.eventType < b.eventType;
  48.         }
  49.         return a.time < b.time;
  50.     }
  51. };
  52.  
  53.  
  54.  
  55. vector<Court> assignCourts(vector<Booking> bookings) {
  56.  
  57.     vector<Event> events;
  58.     for (int i=0;i<bookings.size(); i++) {
  59.  
  60.         Event start(bookings[i].start, bookings[i].bookingId, "start");
  61.         Event end(bookings[i].end, bookings[i].bookingId, "end");
  62.  
  63.         events.push_back(start);
  64.         events.push_back(end);
  65.     }
  66.  
  67.     sort(events.begin(), events.end(), myCmp());
  68.  
  69.  
  70.     int totalNumberOfCourts = 0;
  71.     map<int, vector<int>> courtIdBookingIdList;
  72.  
  73.     for (int i=0; i<events.size(); i++) {
  74.  
  75.         if (events[i].eventType == "start") {
  76.               totalNumberOfCourts++;
  77.               int courtId = totalNumberOfCourts;
  78.               courtIdBookingIdList[courtId].push_back(events[i].bookingId);
  79.         } else {
  80.             totalNumberOfCourts--;
  81.         }
  82.     }
  83.  
  84.  
  85.     vector<Court> answer;
  86.     for(auto it = courtIdBookingIdList.begin(); it!=courtIdBookingIdList.end(); it++){
  87.         Court court(it->first, it->second);
  88.         answer.push_back(court);
  89.     }
  90.  
  91.     return answer;
  92. }
  93.  
  94. int main() {
  95.  
  96.     vector<Booking> bookings;
  97.     bookings.push_back(Booking(101, 1, 4));
  98.     bookings.push_back(Booking(102, 2, 5));
  99.     bookings.push_back(Booking(103, 6, 8));
  100.     bookings.push_back(Booking(104, 3, 7));   
  101.     bookings.push_back(Booking(105, 9, 10));  
  102.  
  103.     vector<Court> answer = assignCourts(bookings);
  104.  
  105.     cout<<"Total Courts Used = "<<answer.size()<<endl;
  106.  
  107.     for(int i=0;i<answer.size();i++){
  108.         int courtId = answer[i].courtId;
  109.         vector<int> bookingIds = answer[i].bookingIds;
  110.  
  111.         for(int i=0;i<bookingIds.size();i++) {
  112.             cout<<"Court Id = "<<courtId<<" BookingId "<<bookingIds[i]<<endl;
  113.         }
  114.     }
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0.01s 5256KB
comments (?)
stdin 
Standard input is empty
stdout 
Total Courts Used = 3
Court Id = 1 BookingId 101
Court Id = 1 BookingId 105
Court Id = 2 BookingId 102
Court Id = 2 BookingId 103
Court Id = 3 BookingId 104
https://ideone.com/Kozo6j
language:
C++ (gcc 8.3)
created:
6 days 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!