I have an array of tasks [begin, end, period].

Each task needs to be completed within the time range from begin to end, and the period is the length of time required to finish the task.

1. The period can be discontinuous time
2. The begin and end are included
3. We can handle an unlimited number of tasks at the same time.

Find the minimum time to process all the tasks

Example: Input:

[[1,3,2],[2,5,3],[5,6,2]]

Output:

4

Explanation:

For tasks[0] we can have time points 2,3
For tasks[1] we can have time points 2, 3, 5 
For tasks[2] we can time points 5, 6

So we only needs to be on at time points 2,3,5 and 6 to complete the task.

My approach:

int process(List<List<Integer>> list) {
    Set<Integer> s = new HashSet<>();
    for(List<Integer> p : list) {
        int period = p.get(p.size()-1);
        List<Integer> other = new ArrayList<>();
        int i=0;
        int s = p.get(0);
        int e = p.get(1);
        for(i=s; i<=e && period >=0; i  ) {
            if(s.contains(i)) {
                period--;
            } else {
                other.add(i);
            }
        }
        if(period != 0) {
            for(i=other.size()-1; i>=0 && period >0; i--, period--) {
                s.add(other.get(i));
            }
        }
    }
    
    return s.size();
}

Here I am trying to add the tasks to a set, and when I have already got the required tasks for a time period I am going to the next task. But my approach is not correct.

What is the correct approach to solving this problem? I am looking for an approach in Java or python.

CodePudding user response：

The computer can handle an unlimited number of tasks at the same time. So you should prioritize the timestamp at which the computer can handle as many as tasks as possible, until all tasks are consumed.

You can follow the steps below.

1. Create a mapping from a discrete timestamp to the number of tasks that can be handled at this time.

   For example, there is only one task (#0) can be handled at timestamp 1, while there are at most two tasks (#0, #1) can be handled at timestamp 2 and timestamp 3.

2. After creating such a mapping, pop the timestamp with the largest number of tasks from it.

   In the above case, we should pop timestamp 2 from the mapping at the first time, and pop timestamp 3 at the next time (next loop).

3. Then, update the remaining period of tasks bound to that timestamp, and update the mapping created at step 1 if necessary.

   Only when a task's remaining period is decreased to 0, do we need to update the mapping by unbinding it from its idle timestamps. This is because a task's period may be less than the duration of its start time and end time. For example, after popping timestamp 2 and timestamp 3, the remaining period of task #0 becomes 0, but there is still a mapping from timestamp 1 to task #0. Therefore we need to remove it.

4. Jump to step 2 until all tasks are completed.

The number of times step 2 is performed is the final result.

Here is an unoptimized sample python code.

tasks = [[1,3,2],[2,5,3],[5,6,2]]

time2task = {}  # Mapping from timestamp to tasks
remaing_period = [period for _, _, period in tasks]

# Step 1.
for tid, (start, end, period) in enumerate(tasks):
    for ts in range(start, end   1):
        time2task.setdefault(ts, set()).add(tid)

busy_ts = []  # busy timestamps
while any(remaing_period):  # Condition of Step 4.
    # Step 2.
    ts, tids = max(time2task.items(), key=lambda item: (len(item[1]), -item[0]))
    time2task.pop(ts)
    busy_ts.append(ts)

    # Step 3.
    for tid in list(tids):
        remaing_period[tid] -= 1
        if remaing_period[tid] == 0:
            # Correct the mapping created at step 1
            start, end, _ = tasks[tid]
            for idle_ts in range(start, end   1):
                if idle_ts in time2task:
                    time2task[idle_ts].remove(tid)
                    if len(time2task[idle_ts]) == 0:
                        time2task.pop(idle_ts)

print(busy_ts)

CodePudding user response：

I think you're over-complicating this. I think the following solution is enough:

int process(List<Integer> list) {
    Set<Integer> s = new HashSet<>();
    for(List<Integer> p : list) {
        int period = p.get(p.size()-1);
        int s = p.get(0);
        int e = p.get(1);
        for(int i=s; i<=e; i  ) {
            s.add(i);
        }
    }

    return s.size();
}

This solution will add all the time points to the set. It's not the most efficient solution, but it's the easiest one to read and understand.