Python | Binary Search | Min-Heap
Intuition\n Describe your first thoughts on how to solve this problem. \nBinary search to get the final answer, use greedy to update the smallest of all the Las
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBinary search to get the final answer, use greedy to update the smallest of all the Last occurrence indexes.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse 2 heap to independently store last occurrence indexes of non-zero and zero parts.\n\n- Only Mark when it is the last element.\n- Update the smallest index of all the non-zero last occurrence indexes.\n\n# Complexity\n- Time complexity: O(mlogm)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n<!-- - Space complexity: -->\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    import heapq\n    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:\n        for i in range(len(changeIndices)):\n            changeIndices[i] -= 1\n        N = len(nums)\n\n        def isPossible(nums, seconds, curIndices) -> bool:\n            markedcnt = 0\n            mp = dict()\n            visited = set()\n            for idx in range(len(curIndices)):\n                mp[curIndices[idx]] = idx\n            hp = [] # store the non-zero part\n            hp2= [] # store the zero part\n            for numidx, lastappear in mp.items():\n                if nums[numidx] != 0:\n                    heapq.heappush(hp, (lastappear, numidx))\n                else:\n                    heapq.heappush(hp2, (lastappear, numidx))\n            for s in range(seconds):\n                curIdx = curIndices[s]\n                if nums[curIdx] == 0 and curIdx not in visited and hp2[0][0] == s:\n                    markedcnt += 1\n                    visited.add(curIdx)\n                    heapq.heappop(hp2)\n                else:\n                    if hp and s == hp[0][0]:\n                        return False\n                    elif hp:\n                        popcnt, pop_numidx = heapq.heappop(hp)\n                        nums[pop_numidx] -= 1\n                        if nums[pop_numidx] != 0:\n                            heapq.heappush(hp, (popcnt, pop_numidx))\n                        else:\n                            heapq.heappush(hp2, (popcnt, pop_numidx))\n            return True if N == markedcnt else False\n\n        left, right = N + sum(nums), len(changeIndices)\n        if left > right:\n            return -1\n        res = float(\'inf\')\n        # binary search\n        while left <= right:\n            mid = (left+right)//2\n            if isPossible(nums[::], mid, changeIndices[:mid]):\n                res = min(res, mid)\n                right = mid-1\n            else:\n                left = mid+1\n        return res if res != float(\'inf\') else -1  \n```
['Python3']