Problem statement

https://binarysearch.com/problems/Minimum-Time-to-Finish-K-Tasks/

Solution

Definitely hard problem. Here is solution by @zdu011 The idea is to start with 2 columns: if we sort pairs, then the max of first column is the last element taken, the max of the second column we keep in heap.

Now for 3 rows, we can still first sort by the 1st column, loop over the tasks and fix the current row, then sort the rows before the current row by their 2nd column and the problem is reduced to the case of only 2 columns.

Complexity

It is O(n^2 log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, tasks, k):
        if not tasks or not k: return 0
        if k == 1: return min(map(sum, tasks))

        tasks = sorted(tasks)
        n = len(tasks)

        ans = inf
        for i in range(k - 1, n):
            m0, m1, m2 = tasks[i]
            h = []
            for v0, v1, v2 in sorted(tasks[:i], key=itemgetter(1)):
                m1 = max(m1, v1)
                heappush(h, -v2)
                if len(h) == k: heappop(h)
                if len(h) == k - 1:
                    ans = min(ans, m0 + m1 + max(m2, -h[0]))
        return ans