Employee Free Time

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.

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.

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.

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.

Test case 1: There is only one problem setter, who is busy during an interval [10, 20]. A day in coding ninjas is given by interval [0, 10^8], thus he will be free between [0, 9] and [21, 10^8] Test case 2: See the problem statement for an explanation.

Brute Force

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’.

Time Complexity

O(T*N*K), where ‘N’ is the number of problem setters, ‘K’ is the maximum number of intervals in the schedule of any problem setter, and ‘T’ is the maximum time i.e (10^8) here.

Here, we check one by one for all time whether all setters are free or not. In order to check whether ‘ith’ setter is free at that time or not, we need to iterate over the list of intervals in which he is working, which will take O(K) time, as there are ‘N’ problem setter then overall it will take O(N*K) time to check whether all setters are free at that time or not. If the maximum time is ‘T’ then overall time complexity will be O(T*N*K).

Space Complexity

O(T), where ‘T’ is the maximum time i.e (10^8) here.

The maximum extra space is used by the array ‘freeTime’ which is of the order of ‘T’. So overall space complexity will be O(T).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation Of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :