Sort+ Greedy vs DP+binary Search||22ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe events[i] has the info (start[i], end[i], value[i]). How to distinguish between sta
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe events[i] has the info (start[i], end[i], value[i]). How to distinguish between `start` and `end` & to find a way keeping correct time ordering?\n\nConsider the info tuple `(time, isEnd, value)`; there are 2 tuples for 1 event. So build an array over the info tuples. Sort it then use Greedy.\n\nFor speed-up, the info tuple can packed into a 64-bit unsigned which is really fast, run in 22 ms beating 100%.\n\nA DP+binary search solution is also made using take or skip argument also applied for solving the hard question [1235. Maximum Profit in Job Scheduling](https://leetcode.com/problems/maximum-profit-in-job-scheduling/solutions/4514682/c-binary-search-dp-99-ms-beats-99-29/)\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Build up an array `time` of size `2*n`\n2. Use a loop to proceed from `i=1` to `n-1`:  `s=events[i][0], e=events[i][1], v=events[i][2]`. let `time[2*i]={s, 0, v};\n            time[2*i+1]={e, 1, v}`\n3. sort `time`\n4. Transverse the sorted `time`\n5. For each iteration, say `[t, isEnd, v]`, if `isEnd` which means it can take `v` for consideration & update `maxV=max(maxV, v)` otherwise update `ans=max(ans, maxV+v)`\n6. 2nd C++ is just packing of info tuple `(time, isEnd, value)` into an `uint64_t` which speeds up probably twice of the speed.\n7.  A recursive DP(memo) with binary search is done which is slow as expected.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n\\log n)$$ \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ \n# Sort+Greedy Code using info tuple||49ms beats 91.89%\n```cpp []\nclass Solution {\npublic:\n    using info=tuple<int, bool, int>;\n    static int maxTwoEvents(vector<vector<int>>& events) {\n        const int n=events.size();\n        vector<info> time(n*2);\n        for(int i=0; i<n; i++){\n            int s=events[i][0], e=events[i][1], v=events[i][2];\n            time[2*i]={s, 0, v};\n            time[2*i+1]={e, 1, v};\n        }\n        sort(time.begin(), time.end());\n        int ans=0, maxV=0, n2=n*2;\n        for(auto& [t, isEnd, v]: time){\n            if (isEnd) maxV=max(maxV, v);\n            else ans=max(ans, maxV+v);\n        }\n        return ans;    \n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# 2nd C++ using Packing info||22ms beats 100%\n```\nclass Solution {\npublic:\n//    using info=tuple<int, bool, int>;\n    static int maxTwoEvents(vector<vector<int>>& events) {\n        const int n=events.size();\n        vector<uint64_t> time(n*2);\n        for(int i=0; i<n; i++){\n            int s=events[i][0], e=events[i][1], v=events[i][2];\n            time[2*i]=((uint64_t)s<<21)+v; // packing\n            time[2*i+1]=((uint64_t)e<<21)+(1<<20)+v;//packing\n        }\n        sort(time.begin(), time.end());\n        int ans=0, maxV=0, n2=n*2;\n        for(auto info: time){\n            bool isEnd=(info>>20)&1; //extract isEnd from info\n            int v=info&((1<<20)-1);  //extract v from info\n            if (isEnd) maxV=max(maxV, v);\n            else ans=max(ans, maxV+v);\n        }\n        return ans;    \n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# Similar to 1235. Maximum Profit in Job Scheduling\nIn that hard question, DP+binary search is applied [ref](https://leetcode.com/problems/maximum-profit-in-job-scheduling/solutions/4514682/c-binary-search-dp-99-ms-beats-99-29/), a similar method is also doable for this medium question, but not fast.\n# C++ using sort+binary Search+DP||135ms Beats 43.24%\n```\nclass Solution {\npublic:\n    int n;\n    int dp[2][100000];// (i, j=index)\n    vector<int> next;\n    int f(int i, int j, vector<vector<int>>& events){\n        if (i>=2 || j>=n) return 0;\n        if (dp[i][j]!=-1) return dp[i][j];\n        int v=events[j][2];\n        int take=v+f(i+1, next[j], events);\n        int skip=f(i, j+1, events);\n        return dp[i][j]=max(take, skip);\n    }\n    int maxTwoEvents(vector<vector<int>>& events) {\n        n=events.size();\n        sort(events.begin(), events.end());\n        next.resize(n);\n        for(int j=0; j<n; j++)\n            next[j]=upper_bound(events.begin()+j, events.end(), vector<int>{events[j][1], INT_MAX, INT_MAX})-events.begin();\n\n        memset(dp, -1, sizeof(dp));\n        return f(0, 0, events);\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Binary Search', 'Dynamic Programming', 'Greedy', 'Bit Manipulation', 'Sorting', 'C++']