CODEWITHSUNDEEP
algorithmsortingdata-structures
Dipak
Dipak

Reputation: 6970

How can I find union of ranges from a multiple group efficiently?

I was creating a report of a common time range in which all the given processes executed concurrently, what I am always doing is drawing a graph and figuring this out manually. Now I have more data and drawing a graph won't be an optimal solution, as a computer engineer, I would like to solve this programmatically, using an optimal and efficient algorithm.

So the question is basically,

There are N processes each has a list of time ranges it has executed, what is the best way to find all the common time intervals in all the given processes was there.

Example:

Let's say there are three processes P1, P2, P3, below is the table giving information about the execution time information of each process:

-|---------|--------------------|-
 | PROCESS |  TIME OF EXECUTION |
-|---------|--------------------|-
 |    P1   |   (0,4) , (5,10)   | **(updated from (0,1) , (5,10))
-|---------|--------------------|-
 |    P2   |   (0,6) , (1,8)    |
-|---------|--------------------|-
 |    P3   |   (3,10)           |
-|---------|--------------------|-

If I draw a graph using each process in the Y-axis and time-range in X-axis I can get something like this below, and the common range is highlighted with blue border color in it.

Graph representing the process vs time ranges NOTE: P1 values are (0, 4) and (5,10)

From the graph, it's obvious the output/result is [ (3, 4), (5, 8) ].

I am looking for a solution/algorithm to deduce these results from the given input. I would appreciate an answer that addresses the following aspects the problem:

Upvotes: 0

Views: 87

Answers (2)

Moon President
Moon President

Reputation: 98

If you have discrete timesteps, a 2 pass method you can use is to generate an array with N timesteps, where N is the number length of time you are watching over divided by the timesteps (i.e. for a 1ms period with a discrete timestep 10us would have N=101) and then go through all of your execution start/stop pairs. Whenever a process starts, add 1 to that timestep of the array, whenever a process stops, minus one from a timestep. Some will be negative, some will be positive, the sum of all elements should be zero.

Next, create an integer, we will call it process_count. It starts at 0. You iterate over the array, adding the value to the process_count each time. Whenever the process_count is equal to the total number of processes that will be running, you have found your rectangle.

Psuedocode:

//Create empty array to store value
array = zeroes(N)

//Assign each timestep the net change in number of running processes
for(tuple in process_runtimes):
    array[tuple[0]] += 1
    array[tuple[1]] -= 1

//Create array to store periods of all programs being on, tuple for individual periods and flag for state machine processing
all_on_periods = []
current_tuple = (0, 0)
on_flag = 0
process_count = 0

//Iterate over array to calculate for each timestep the number of processes running.
for i in range(len(array)):
    process_count += val[i]
    
    //If all processes are running, create a tuple that tracks the beginning of the block where they are all running
    if(process_count == total_processes and on_flag == 0):
        on_flag = 1
        current_tuple[0] = i

    //Else, if all processes were running but aren't running any longer, enter the last timestamp they were all running on.
    elseif(process_count == total_processes and on_flag == 0):
        on_flag = 0
        current_tuple[1] = i - 1
        all_on_periods.append(current_tuple)

I don't think this is dynamic programming, but I am not an authority on that.

While similar to the Largest Histogram problem, this is also fairly distinct. This is about concurrency with a binary check, while the histogram problem is about searching for rectangles and comparing sizes.

Upvotes: 1

Phenomenal One
Phenomenal One

Reputation: 2587

This can be solved by maintaining a prefix sum and checking its count.

But before this, you need to some basic prepocessing.

For each time of execution for a process , you need to merge the overlapping intervals.

This is a very common algo which you could look it up.

So, after this step, your input becomes,

-|---------|--------------------|-
 | PROCESS |  TIME OF EXECUTION |
-|---------|--------------------|-
 |    P1   |   (0,4) , (5,10)   |
-|---------|--------------------|-
 |    P2   |   (0,8)            |
-|---------|--------------------|-
 |    P3   |   (3,10)           |
-|---------|--------------------|-

For P2 what we have done here is merge (0,6) and (1,8) and made it as (0,8).

Now, the next step is the actual algorithm to calculate prefix sum.

It works in the following way.

1. initialize a map
2. for each start_time,end_time.
      map[start_time++] and map[[(end_time+1)]--]

Reason for (end_time+1) is because the process runs till end_time. After this end_time , we can remove its count from our list.

So, now we have our values.

0 2
3 1
5 0
9 -1
11 -2

Now, we can start couting the prefix sums.

To do this, we initialize a counter sum=0. and have the keys of map in sorted order.

num_processes=3 is initialized as well!. `

at 0, val = 2 , sum =2 (!=3) .(start=-1 and end =-1)
at 3, val = 1,  sum =3 // intersection start (start=3, end=-1)
at 5, val = 0,  sum =3 (remains same) // intersection end and start new one (add (3,4) and (start=5,end=-1) 
at 9 , val = -1, sum = 2 // intersection end (add 5,8) (start=-1 and end =-1)
at 11, val = -2, sum = 0 // (start=-1 and end =-1)

add (3,4),(5,8) to the final result.

Upvotes: 2

Related Questions