986. Interval List Intersections

Question

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Solutions

Method 1: Sort head and tail sparately

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        int len = A.length + B.length;
        int[] starts = new int[len];
        int[] ends = new int[len];
        for(int i = 0; i < A.length; i++){
            starts[i] = A[i][0];
            ends[i] = A[i][1];
        }
        for(int i = A.length; i < A.length + B.length; i++){
            starts[i] = B[i - A.length][0];
            ends[i] = B[i - A.length][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        List<int[]> res = new ArrayList<>();
        for(int i = 1; i < starts.length; i++){
            if(starts[i] <= ends[i - 1]){
                res.add(new int[]{starts[i], ends[i - 1]});
            }
        }
        int size = res.size();
        int[][] result = new int[size][2];
        for(int i = 0; i < size; i++){
            result[i] = res.get(i);
        }
        return result;
    }
}

Method 2: Sort with head and tail together.

  class Solution {
      public int[][] intervalIntersection(int[][] A, int[][] B) {
          int len = A.length + B.length;
          if(len == 0) return new int[0][2];
          int[][] arr = new int[len][2];
          for(int i = 0; i < A.length; i++)   arr[i] = A[i];
          for(int i = A.length; i < len; i++) arr[i] = B[i - A.length];
          Arrays.sort(arr, (a, b)->{
              return a[0] == b[0] ? a[1] - b[1]: a[0] - b[0];
          });
          int end = arr[0][1];
          List<int[]> res = new ArrayList<>();
          for(int i = 1; i < len; i++){
              if(arr[i][0] <= end){
                  res.add(new int[]{arr[i][0], Math.min(arr[i][1], end)});
              }
              if(end < arr[i][1])
                  end = arr[i][1];
          }
          int size = res.size();
          int[][] result = new int[size][2];
          for(int i = 0; i < size; i++) result[i] = res.get(i);
          return result;
      }
  }