Maximum number of tasks to be performed

user_11500177 0
Viewed 8080

I'm stucking in a problem. I know dp can be applied here, but not getting it.

Consider a part of the positive number line starting at 0 and ending at 10^9. You start at 0 and there are N tasks can be performed.

The ith task is at l[i] and requires t[i] time to be performed. To perform ith task, you've to reach the point l[i] and spend time t[i] at that location.

It takes one second to travel one unit on the path i.e. going from 1 to 3 will take (3 - 1) = 2 seconds.

You are given T seconds of time, in this time you have to perform as many as tasks you can AND return to the start position. I need to find maximum can be performed in time T.

Example

Consider M = 3, T = 10, and l[] = [1, 2], and t[] = [3, 2].

If we perform the 1st task total time consumed is 1 (to travel) + 3 (to do the task) = 4. The remaining time is 10 - 4 = 6.

Now if we perform the 2nd task consecutively, the total time taken is 1 (to travel from 1) + 2 (to do the task) = 3. The time remaining is 6 - 3 = 3.

Now if we return from 2 to 0. The total time taken is 2. The remaining time is 3 - 2 = 1. Therefore we can safely complete both tasks in a given time. So the answer is 2.

Constrains are high:

1 <= N <= 10 ^ 5
0 <= T <= 10 ^ 8
0 <= l[i], t[i] <= 10 ^ 9
dynamic-programming data-structures arrays algorithm java
1 Answers

There is an optimal solution where we travel from 0 to some coordinate x and back, greedily choosing tasks in the interval [0, x] from shortest to longest.

There might be a dynamic programming solution, but it's not what I would reach for first. Rather, I'd use a sweep-line algorithm that increases x from 0 to T/2, maintaining an optimal solution. When x passes l[i], we add task i to the agenda. Whenever the current agenda uses too much time, we drop the longest task.

The algorithm looks something like this in Python (untested).

import heapq


def max_tasks(T, l, t):
    x = 0
    heap = []
    opt = 0
    # Sweep the tasks left to right
    for l_i, t_i in sorted(zip(l, t)):
        # Increase x to l_i
        T -= 2 * (l_i - x)
        x = l_i
        # Add task i to the agenda
        T -= t_i
        # This is a min-heap, but we want the longest tasks first
        heapq.heappush(heap, -t_i)
        # Address a time deficit by dropping tasks
        while T < 0:
            if not heap:
                # Travelled so far we can't do any tasks
                return opt
            # Subtract because the heap elements are minus the task lengths
            T -= heapq.heappop(heap)
        # Update the optimal solution so far
        opt = max(opt, len(heap))
    return opt
user_21446690
Related