Event driven simulation using priority queue implemented with binary heap

Question

I need to simulate the execution of a set of tasks that are given. This means that you need to keep track of which tasks are active at any given point in time, and remove them from the active list as they finish.

I need to use priority queue for this problem, to be implemented using binary heap.

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

3
2 5
4 23
7 4

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

1. Max number of active tasks at any given time (2 in this case) and
2. 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

I've written the following code to read in the time values into a structure:

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

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

int main()
{
    long int num_tasks;
    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);
        t[i].end = t[i].start + t[i].dur;
    }
}

I would like to understand how this can be implemented as a heap priority queue and to obtain the necessary outputs from the heap.

Answer 1

This problem can be solved by using two heaps, one that contains start times, and the other contains end times. When reading the tasks, add the start and end times to the two heaps. Then the algorithm looks like this:

number_of_tasks = 0

while start_heap not empty
    if min_start_time < min_end_time
       pop min_start_time
       number_of_tasks += 1    
    else if min_end_time < min_start_time
       pop min_end_time
       number_of_tasks -= 1
    else 
       pop min_start_time
       pop min_end_time

while end_heap not empty
       pop min_end_time
       number_of_tasks -= 1