leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

non-overlapping.cpp (1296B)

      1 #include <unordered_map>
      2 #include <iostream>
      3 #include <vector>
      4 #include <algorithm>
      5 
      6 class Solution {
      7 public:
      8     int maxTwoEvents(vector<vector<int>>& events){
      9 
     10         std::sort(events.begin(), events.end());
     11         vector<int> best;
     12 
     13         int max = 0;
     14         for(int i = 0 ; i < events.size(); ++i){
     15             if(events[i][1] > max){
     16                 max = events[i][1];
     17             }
     18         }
     19 
     20         // iterate to max and pushback
     21         for(int i = 0 ; i < max; ++i){
     22             best.push_back(0);
     23         }
     24         best.push_back(0);
     25         best.push_back(0);
     26 
     27         int retScore = 0;
     28 
     29         for (int i = 0 ; i < events.size(); ++i){
     30             vector<int> currentEvent = events[i];
     31             int lowerBound = currentEvent[0];
     32             int currentVal = currentEvent[2];
     33             int bestAtLocation = best[lowerBound];
     34 
     35             if (bestAtLocation + currentVal > retScore){
     36                 retScore = bestAtLocation + currentVal;
     37             }
     38             if(currentVal > best[currentEvent[1] + 1]){
     39                 for(int x = currentEvent[1] + 1; x < best.size(); ++x){
     40                     if(currentVal > best[x]){
     41                         best[x] = currentVal;
     42                     }
     43                 }
     44             }
     45         }
     46 
     47         return retScore;
     48     }
     49 };