1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution:
def minimumTime(self, nums1: List[int], nums2: List[int], target: int) -> int:
array_length = len(nums1)
indices = list(range(array_length))
total_sum, total_increment = 0, 0
for i in range(array_length):
total_sum += nums1[i]
total_increment += nums2[i]
if total_sum <= target:
return 0
# Custom comparator for sorting indices based on nums2 values
indices.sort(key=lambda i: nums2[i])
# Dynamic programming array to keep track of sums
sum_array = [0] * (array_length + 1)
# Variable to keep track of result
result = array_length + 1
for i in range(1, array_length + 1):
for j in range(min(i, result - 1), 0, -1):
sum_array[j] = max(sum_array[j], sum_array[j - 1] + nums2[indices[i - 1]] * j + nums1[indices[i - 1]])
if total_sum + j * total_increment - sum_array[j] <= target:
result = j
return result if result <= array_length else -1
|