Sort + greedy + DP problem, beat 100% C++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n    \n# Approach\n Describe your approach to solving the problem. \n    sum = sum(num
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n    \n# Approach\n<!-- Describe your approach to solving the problem. -->\n    sum = sum(nums1) + t * sums(nums2)\n    Create a table:\n    - Each row is values of nums1 after adding nums2 at time t\n    - Element is sort by nums2\n\n```\nnums1   5   4   6   7\nnums2   1   2   3   4\n\nt = 1   6   6   9   11\nt = 2   7   8   12  15\nt = 3   8   10  15  19\n```\n\nAt time t, need to find subset of t elements from each row, elements must have distinct column index.\n\nSum of element is value removed from total sum, our work is choosing maximum sum and check if sum of subset >= total sum - x \n\nGreedy property:\nDelete num with bigger nums2 later to maximize value.\nSo if we choose num[i] when t = 1, only choose nums[j], j > i when t = 2 and so on.\n\nAt row 1, we need to find maximum num. Store maximum num in dp[0][j]\n\nAt row 2, for each num[j], need to find maximum num from row 1 which index < j. Store maximum duel nums so far in dp[1][j];\n\nAt row i, assume we choose num[j], we need to find maximum sum of i - 1 num from row 1 -> i - 1, which is stored by dp[i - 1][j - 1]\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    dp table can be simplified to a vector since we only need the last row\n    O(n)\n# Code\n```\nclass Solution {\npublic:\n    int minimumTime(vector<int>& nums, vector<int>& delta, int x) {\n        int n = nums.size();\n\n        vector<vector<int>> arr(n, vector<int>(2));\n        for (int i = 0; i < n; ++i) {\n            arr[i][0] = delta[i];\n            arr[i][1] = nums[i];\n        }\n        std::sort(arr.begin(), arr.end());\n        \n        int sumNums = 0, sumDelta = 0;\n        for (int i = 0; i < n; ++i) {\n            delta[i] = arr[i][0];\n            nums[i] = arr[i][1];\n            sumNums += nums[i];\n            sumDelta += delta[i];\n        }\n        \n        if (sumNums <= x) return 0;\n        \n        vector<int> dp(n, 0);\n        int curMax = 0;\n        for (int i = 0; i < n; ++i) {\n            curMax = std::max(curMax, nums[i] + delta[i]);\n            dp[i] = curMax;\n            if (dp[i] >= sumNums + sumDelta - x) return 1;\n        }\n\n        int sum = 0;\n        for (int i = 2; i <= n; ++i) {\n            sum = sumNums + i * sumDelta;\n            \n            curMax = 0;\n            vector<int> tempDp(n, 0);\n            for (int j = i - 1; j < n; ++j) {\n                int val = nums[j] + i*delta[j];\n                curMax = std::max(curMax, val + dp[j - 1]);\n                if (curMax >= sum - x) return i;\n                tempDp[j] = curMax;\n            }\n            for (int j = 0; j < n; ++j) dp[j] = tempDp[j];\n        }\n        \n        return -1;\n    }\n};\n```
['C++']