# Maximum number of tasks to be performed

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
```

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

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
T -= t_i
# This is a min-heap, but we want the longest tasks first
heapq.heappush(heap, -t_i)