Binary Search + Greedy
Intuition\n- Come up with a solution for sub problem changeIndices[0,end]\n- Do binary search\n\n\n# Approach\n1. greedy marking (as late as possible)\n2. accum
# Intuition\n- Come up with a solution for sub problem changeIndices[0,end]\n- Do binary search\n\n\n# Approach\n1. greedy marking (as late as possible)\n2. accumulate decrease as token to be used/updated at marking\n3. binary search\n# Complexity\n- Time complexity:\nO(m longm)\n\n# Code\n```\n\nclass Solution {\npublic:\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {\n        int n = nums.size(), m = changeIndices.size();\n        using Index = int;\n        using Time = int;\n        auto canMark = [&nums, &changeIndices] (int end) {  // sub problem of changeIndices[0, end]\n            unordered_map<Index, Time> lastChange; \n            int token = 0, marked = 0;\n            for(int i = 0; i <= end; ++i) \n                lastChange[changeIndices[i] - 1] = i;\n            for(int i = 0; i <= end; ++i) {\n                if(auto idx = changeIndices[i] - 1; i == lastChange[idx]) {\n                    if(token >= nums[idx]) {\n                        token -= nums[idx];\n                        ++marked;\n                    }\n                    else\n                        return false;\n                }\n                else\n                    token++;\n            }\n            return marked == nums.size();\n        };\n        if(!canMark(m-1)) return -1;\n        if(canMark(0)) return 1;\n        int hi = m-1;\n        for(int lo = 0; lo+1 < hi; ) {\n            int mid = (lo + hi) / 2;\n            if(canMark(mid))\n                hi = mid;\n            else\n                lo = mid;\n        }\n        return hi + 1;\n    }\n};\n```
['C++']