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

## Answer

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