Employee Free Time

PROBLEM STATEMENT

There are ‘N’ Problem Setters in Coding Ninjas, Each of them has a unique id between 0 to N-1. A Problem Setter works in multiple non-overlapping time intervals during a day.

Formally, A Problem Setter having id ‘i’ works in ‘Ki’ non-overlapping intervals of the form [T1, T2], [T3, T4] ... [T(2ki-2), T(2ki-1)], where Ti is in between [0, 10^8] and Ti <= T(i+1). A day in Coding ninjas start from time 0 and end at time 10^8 (both inclusive).

You are given ‘N’ sorted lists of non-overlapping intervals, where the ith list gives a schedule (list of intervals in which the problem setter works) of a Problem Setter having id ‘i’. Your task is to find a sorted list of non-overlapping intervals in which all problem setters are free. If there are multiple possible such lists, output the list which is minimum in length.

Note :

1. In sorted order interval [T1, T2] comes before [T3, T4] if either T1 < T3, or (T1 == T3  and T2 < T4).
2. An interval [T1, T2] represents, time T1, T1+1, T1+2, ... T2, i.e all integers between T1, T2 both T1 and T2 inclusive.  
3. For simplicity, we represent the list of intervals in a 1D array where every two numbers show an interval, i.e list [1, 3, 5, 7, 9, 11] represent intervals [1, 3], [5, 7] and [9, 11] 
4. It is guaranteed that there will be at least one interval where all problem setters are free.

Example :

Let suppose there are 3 problem setters, their working intervals are represented by the following list of lists, ‘Schedules’: [[1, 2, 5, 6], [1,2], [5, 10]], where the ith interval of a setter is represented by 2*i and (2*i+1)th integer in their respective list,  I.e. Problem Setter with an id 0, works in the intervals [1, 2], [5, 6]. Problem Setter with an id 1, work in the interval  [1,2]. Problem Setter with id 2, works in the interval [5, 10], 
In this example, the time intervals where setter 0 is free are [0, 0], [3, 4], [7, 10^8]
And the time intervals where setter 1 is free are [0, 0], [3, 10^8].
And the time intervals where setter 2 is free are [0, 4], [11, 10^8].
We can clearly observe that time intervals, where all 3 setters are free are, [0, 0], [3, 4], and [11, 10^8].  
Thus we should output a list [0, 0, 3, 4, 11, 10^8] that represents these lists in 1D array form as described in notes. It can be shown easily, that this is the minimum possible length list of intervals representing common free time.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases, then ‘T’ test cases follow.

The first line of each test case consists of a single integer ‘N’ representing the number of problem setters.

Then 2*‘N’ line follows, which gives the ‘schedule’ of each of the problem setters. The 2*i+1th line consist of single even integer ‘Ki’ representing the number of intervals of ith problem setter and (2*i+2)th line consist of 2*Ki space-separated integers representing the list of intervals in a 1-D array.

Output Format :

For each test case, in a separate line print the smallest and sorted list of non-overlapping intervals that give the common free time of ‘N’ problem setters. I.e if there are ‘K’ such intervals, then you need to print 2*K space-separated integers representing this list in a 1-D array.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1  <= N <= 1000
1 <= K <= 1000

Time limit: 1 sec

Approach 1

We will iterate from 0 to 10^8, and for each of the time points, we will iterate in the schedule of each of the ‘N’ problem setters and check whether they are free at that time or not. We will insert all these time-intervals in a list and group the consecutive time in a single interval.

Algorithm

Create an empty list of integers ‘freeTime’.
Run a loop where ‘i’ ranges from 0 to 10^8, and for each ‘i’ do the following.
- Initialize a boolean variable ‘isFree’:= true.
- Run a loop where ‘j’ ranges from 0 to N-1 and for each ‘j’ do the following
  - Iterate over all the intervals in which the jth employee is working and check whether ‘i’ is between this interval or not, if ‘i’ is in between this interval that assigns ‘isFree’:= false. And then break this loop
- If ‘isFree’ is true append integer ‘i’ in the list ‘freeTime’.
Create a list of integers ‘result’ and push freeTime[0] in it.
Run a loop where ‘i’ ranges from 1 to freeTime.length-1 and if freeTime[i] != freeTime[i-1]+1, then insert both freeTime[i-1] and freeTime[i] in the list
Push the last element of the list ‘freeTime’ in ‘result’.
Return ‘result’.

Try Problem

Approach 2

We will iterate from 0 to 10^8, and for each of the time points, we will use binary search in the schedule (Note schedule of each setter is sorted) of each of the ‘N’ problem setters to check whether they are free at that time or not. We will insert all these time-intervals in a list and group the consecutive time in a single interval.

Algorithm

Create an empty list of integers ‘freeTime’.
Run a loop where ‘i’ ranges from 0 to 10^8, and for each ‘i’ do the following.
- Initialize a boolean variable ‘isFree’:= true.
- Run a loop where ‘j’ ranges from 0 to N-1 and for each ‘j’ do the following
  - Use binary search to find out the lower bound of integer ‘i’ in list Schedules[j], let ‘p’ be the index of this lower bound (0 based indexing) then if ‘p’ is not even or integer at index ‘p’ is not equal to ‘i’ then it means ‘j’th setter is not free at that time, otherwise he will be free. Note -: lower bound of the integer is the smallest integer greater than or equal to that integer in the list. If lower_bound doesn’t exist then setter will be free at that time.
- If ‘isFree’ is true append integer ‘i’ in the list ‘freeTime’.
Create a list of integers ‘result’ and push freeTime[0] in it.
Run a loop where ‘i’ ranges from 1 to freeTime.length and if freeTime[i] != freeTime[i-1]+1, then insert both freeTime[i-1] and freeTime[i] in the list
Push the last element of the list ‘freeTime’ in ‘result’.
Return ‘result’.

Try Problem

Approach 3

We will create a boolean array of size ‘10^8’ and fill it with true. This array represents whether all setters are free at a particular time or not. We will then iterate over each interval present in the schedule of each of the N problem setters. While iterating over the interval, we will mark false at the index corresponding to that time point of that interval in the boolean array to indicate all setters are not free at that interval.

Algorithm

Create a boolean array ‘freeTime’ of size 10^8+1 and fill it with true.
Run a loop where ‘i’ ranges from 0 to N-1, and for each ‘i’ do the following.
- Run a loop where ‘j’ ranges from 0 to Schedules[i].length -1 and for each of the even value of ‘j’ do the following -:
  - Run a loop where ‘t’ ranges from Schedules[i][j] to Schedules[i][j+1] and for each of the ‘t’ mark freeTime[‘t’] := false.
Create a list of integers ‘result’.
Run a loop where ‘i’ ranges from 0 to 10^8 and if freeTime[i] = true and (freeTime[i-1] = false or i = 0), then insert ‘i’ in result as it implies a new interval is started, similarly, if freeTime[i] = true and (freeTime[i+1] = false or i = 1e8), then insert ‘i’ in result as it indicate ending of an interval.
Return ‘result’.

Try Problem

Approach 4

Note that there are N*K intervals, where ‘N’ is the number of problem setters and ‘K’ is the maximum number of intervals in the schedule of any setter. Since each interval can be represented by only 2 integers, thus we will have at most 2*N*K integers representing intervals in which at least problem setter is working, Similarly we will have 2*N*K integers intervals in which some problem setter is not working (interval between two working intervals is a free interval for a problem setter), Thus overall we will have at max 4*N*K+2 integers representing busy or free intervals of problem setters. (We also include 0 and 10^8 ), So we can map all these integers to some unique integer between 0 to 4*N*K+2. To do this we will first create a list consisting of all these integers and then sort this list in non-decreasing order. After this, we will map each of these integers to some smaller integers such that their relative magnitude will remain the same, and replace all the intervals in the schedule using these mapped values. This technique is called coordinate compression.

After coordinate compression, let say that the maximum integer in intervals is ‘M’, clearly M <= 4*N*K+2, We will then create an integer array of size ‘M’+1, let's name it busySetters, such that busySetters[t] will give a number of Problem Setters that are busy at a time ‘t’. Note ‘t’ will be a compressed value. Initially, we fill this array with 0.

After that, we iterate over all the intervals in schedules of each of the problem setters and for each interval [x, y] we will increment all the indexes between [x, y] by ‘1’ as one more problem setter is busy at these times. We can do it efficiently by only incrementing busySetters[x] by 1 and decrement busySetters[y+1] by 1 for each interval [x, y]. The number of Problem Setters that are busy at any time ‘t’ will be the sum of first ‘t’ integers in busySetters. This technique is also known as a difference array.

Clearly, all setters are free at time ‘t’, if busySetters[t] = 0, Lastly we will combine consecutive free times in intervals.

Algorithm

Create a list ‘coordinates’ and insert all those integers that are used to represent all the intervals (both where the problem setter is working or the problem setter is free).
Sort the list ‘coordinates’ and remove duplicates.
Create a HashMap and insert all integers present in array coordinates mapped with their index in the array coordinates.
Replace all the intervals in the schedule of each of the ‘N’ problem using the mapped value of the integers representing them
Create an array ‘busySetters’ of size coordinates.length+1.
Run a loop where ‘i’ ranges from 0 to N-1 and do the following.
- Iterate over all the intervals present in the schedule of setter with id ‘i’, and for each interval [x, y] increment busySetters[x] by 1 and decrement busySetters[y+1] by 1.
Run a loop where ‘i’ ranges from 1 to coordinates.length+1 and do busySetters[i] += busySetters[i-1].
Create a list of integers ‘result’.
Run a loop where ‘i’ ranges from 0 to coordinates.length and if busySetter[i] = 0 and (busySetter[i-1] != 0 or i = 0), then insert ‘i’ in result as it implies a new interval is started, similarly, if busySetter[i] = 0 and (busySetter[i+1] = 0 or i+1 = coordinates.length), then insert ‘i’ in result as it indicate ending of an interval.
Replace each integer ‘x’ in the array ‘result’ with ‘coordinates[x]’.
Return ‘result’.