Counting active tasks using start time and duration in C++

The input consists of a set of tasks given in increasing order of start time, and each task has a certain duration associated. The first line is number of tasks, for example

This means that there are 3 tasks. The first one starts at time 2, and ends at 7 (2+5). Second starts at 4, ends at 27. Third starts at 7, ends at 11. We assume each task starts as soon as it is ready, and does not need to wait for a processor or anything else to free up. This means we can keep track of number of active tasks:

Time       #tasks
0 - 2        0
2 - 4        1
4 - 11       2
11 - 27      1

I need to find 2 numbers:

Max number of active tasks at any given time (2 in this case) and
Average number of active tasks over the entire duration computed here as :

[ 0*(2-0) + 1*(4-2) + 2*(11-4) + 1*(27-11) ] / 27

For this, I have first found the time when all tasks have come to an end using the below code:

#include "stdio.h"
#include "stdlib.h"

typedef struct
{
    long int start;
    int dur;
} task;

int main()
{
    long int num_tasks, endtime;
    long int maxtime = 0;
    scanf("%ld",&num_tasks);
    task *t = new task[num_tasks];
    for (int i=0;i<num_tasks;i++)
    {
        scanf("%ld %d",&t[i].start,&t[i].dur);
        endtime = t[i].start + t[i].dur;
        if (endtime > maxtime)
            maxtime = endtime;
    }
    printf("%ld\n",maxtime);
}

Can this be done using Priority Queues implemented as heaps ?

Solution

Your question is rather broad, so I am going to just give you a teaser answer that will, hopefully, get you started, attempting to answer your first part of the question, with a not necessarily optimized solution.

In your toy input, you have:

2 5
4 23
7 4

thus you can compute and store in the array of structs that you have, the end time of a task, rather than its duration, for later usage. That gives as an array like this:

2 7
4 27
7 11

Your array is already sorted (because the input is given in that order) by start time, and that's useful. Use std::sort to sort the array, if needed.

Observe how you could check for the end time of the first task versus the start time of the other tasks. With the right comparison, you can determine the number of active tasks along with the first task. Checking whether the end time of the first task is greater than the start time of the second task, if true, denotes that these two tasks are active together at some point.

Then you would do the same for the comparison of the first with the third task. After that you would know how many tasks were active in relation with the first task.

Afterwards, you are going to follow the same procedure for the second task, and so on.

Putting all that together in code, we get:

#include "stdio.h"
#include "stdlib.h"
#include <algorithm>

typedef struct {
    int start;
    int dur;
    int end;
} task;

int compare (const task& a, const task& b) {
    return ( a.start < b.start );
}

int main() {
    int num_tasks;
    scanf("%d",&num_tasks);
    task *t = new task[num_tasks];
    for (int i=0;i<num_tasks;i++) {
        scanf("%d %d",&t[i].start,&t[i].dur);
        t[i].end = t[i].start + t[i].dur;
    }
    std::sort(t, t + num_tasks, compare);
    for (int i=0;i<num_tasks;i++) {
        printf("%d %d\n", t[i].start, t[i].end); 
    }
    int max_noOf_tasks = 0;
    for(int i = 0; i < num_tasks - 1; i++) {
        int noOf_tasks = 1;
        for(int j = i + 1; j < num_tasks; j++) {
            if(t[i].end > t[j].start)
                noOf_tasks++;
        }
        if(max_noOf_tasks < noOf_tasks)
            max_noOf_tasks = noOf_tasks;
    }
    printf("Max. number of active tasks: %d\n", max_noOf_tasks);
    delete [] t;
}

Output:

2 7
4 27
7 11
Max. number of active tasks: 2

Now, good luck with the second part of your question.

PS: Since this is C++, you could have used an std::vector to store your structs, rather than a plain array. That way you would avoid dynamic memory allocation too, since the vector takes care that for you automatically.