Python Beats 99%, Binary Search Answer, Greedy (heap)
Intuition\nSee comments. The main idea is to notice that we delay marking until last possible second so that we have enough time to perform op1. To implement th
# Intuition\nSee comments. The main idea is to notice that we delay marking until last possible second so that we have enough time to perform op1. To implement this we use heap to dynamcially get next \'ddl\' to meet. \n\n# Approach\ncheck(t) checks if we can done in t seconds (0-indexed)\nThen we know for t from small to larger (0 to m-1) check(t) will return ...FFFTTT..., we want the first \'True\' which is the earliest possible time to be done. Remember to cast back to 1-indexing at the end.\n\n# Complexity\n- Time complexity:\nO(m log m)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:\n        n, m = len(nums), len(changeIndices)\n        def check(t):   # if can done in t seconds (0-indexed)\n            # KEYOBS: only mark at last possible seconds\n            last = collections.defaultdict(int)\n            for i in range(t + 1): \n                last[changeIndices[i]] = i\n            if len(last) < n: return False  # cannot possible mark all\n            # now need to check from earliest "last"\n            heap = []   # (last, val)\n            for k, v in last.items():\n                heappush(heap, (v, k))\n            # greedy check availaibility\n            budget = 0      # free budget to perform op1\n            currTime = 0    # current time stamp (0-indexed)\n            while heap:\n                last, idx = heappop(heap)\n                op1Needed = nums[idx - 1]\n                timeAvail = last - currTime\n                if timeAvail + budget < op1Needed: return False   # cannot possibly mark nums[idx-1]\n                op1Needed -= budget             # use budget\n                budget = timeAvail - op1Needed  # new budget\n                currTime = last + 1\n            return True\n        # binary search ans set (FFFTTT) first T\n        ans, left, right = -2, 0, m - 1  \n        while left <= right:\n            mid = (left + right) // 2\n            if check(mid): \n                ans = mid\n                right = mid - 1\n            else:\n                left = mid + 1\n        return ans + 1  # cast back to 1-indexed\n\n```
['Binary Search', 'Greedy', 'Heap (Priority Queue)', 'Python3']