986. Interval List Intersections

Link

Solution

依照merge sort的原則，同時追蹤兩指標，merge能有intersection的interval

並將endpoint比較小的在下一輪中移調

    public int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> ret = new ArrayList<>();
        
        int i = 0, j = 0;
        while(i < A.length && j < B.length){
            
            int lo = Math.max(A[i][0], B[j][0]);
            int hi = Math.min(A[i][1], B[j][1]);
            if(lo <= hi){
                ret.add(new int[]{lo, hi});
            }
            
            //remove the lower end interval
            if(A[i][1] < B[j][1]){
                i++;
            }else{
                j++;
            }
        }
        return ret.toArray(new int[ret.size()][]);
    }