leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0732.cpp (901B)

      1 // Map solution
      2 class MyCalendarThree {
      3     map<int, int> mp;
      4 
      5   public:
      6     int book(int startTime, int endTime) {
      7         mp[startTime]++;
      8         mp[endTime]--;
      9 
     10         int res = 0, acc = 0;
     11         for (const auto [_, add] : mp) {
     12             res = max(res, acc += add);
     13         }
     14 
     15         return res;
     16     }
     17 };
     18 
     19 // Vector solution
     20 class MyCalendarThree {
     21     using type_t = pair<int, int>;
     22     vector<type_t> vec;
     23 
     24   public:
     25     int book(int startTime, int endTime) {
     26         const type_t start = {startTime, 1};
     27         const type_t end = {endTime, -1};
     28 
     29         // trick to insert into a sorted vector
     30         vec.insert(upper_bound(vec.begin(), vec.end(), start), start);
     31 
     32         vec.insert(upper_bound(vec.begin(), vec.end(), end), end);
     33 
     34         int res = 0, acc = 0;
     35         for (const auto [_, add] : vec) {
     36             res = max(res, acc += add);
     37         }
     38 
     39         return res;
     40     }
     41 };