DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Interval list intersections

Problem

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)