Tc : O(nlogn) for sorting the list + O(n) for traversal of the list
Sc: O(n) for using the list O(2k) for using result list and res[] array
//same as merge intervals
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
//put both the list in a single list 'list'
List<int[]> list = new ArrayList<>();
for(int i =0;i<firstList.length;i++){
list.add(new int[]{firstList[i][0],firstList[i][1]});
}
for(int i =0;i<secondList.length;i++){
list.add(new int[]{secondList[i][0],secondList[i][1]});
}
//sort the 'list' in ascending order of the start time
Collections.sort(list,(a,b)->{
if(a[0]==b[0]) return Integer.compare(b[1],a[1]);// if the start time is same sort on the basis on ending time
return Integer.compare(a[0],b[0]); //else sort on the basis of start time
});
//below is same as mergeInterval problem:solved greedly
int start = Integer.MAX_VALUE;
int end = Integer.MIN_VALUE;
List<int[]> result = new ArrayList<>();
for(int i =0;i<list.size();i++){
int intervals[] = list.get(i);
//case 1 : (a,b) and (p,q) where p is between (a,b) and b is between (p,q) so intersection will be : (p,b)
if(end>=intervals[0] && end<= intervals[1]){
result.add(new int[]{intervals[0],end});
start = Integer.min(start, intervals[0]);
end = Integer.max(end, intervals[1]);
}
//case 2 : (a,b) and (p,q) and p,q both lie between (a,b)
else if(end>=intervals[0] && end>=intervals[1]){
result.add(new int[]{intervals[0],intervals[1]});
}
else{
start = intervals[0];
end = intervals[1];
}
}
int res[][] = new int[result.size()][2];
for(int i= 0;i<result.size();i++){
res[i] = result.get(i);
}
return res;
}
}