986. Interval List Intersections

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

notice! should declare

List<int[]>

use int[] is easy to transform to array , Integer[] cant be done by toArray(),

Map<int, int> map = new HashMap<>(); // wrong!
List<int> list = new ArrayList<>(); // wrong!

Map<Integer, Integer> map = new HashMap<>(); // ok

List<int[]> list = new ArrayList<>(); // ok, it's int array

it needs to use list.stream().mapToInt(i->i).toArray();

return result.toArray(new int[result.size()][]);

Time Complexity: O(M+N), where M,N are the lengths of A and B respectively.

Space Complexity: O(M+N), the maximum size of the answer.

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        // use two points
        // find startMax, endMin
        
        int i = 0; // A's index
        int j = 0; // B's index
        
        List<int[]> result = new ArrayList<>();
        
        while (i < A.length && j < B.length) {
            
            int startMax = Math.max(A[i][0], B[j][0]);
            int endMin = Math.min(A[i][1], B[j][1]);
            
            if (endMin >= startMax) {
                result.add(new int[]{startMax, endMin});
            }
            
            if (A[i][1] < B[j][1]) {
                i++;
            } else {
                j++;
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}

latest version

```java
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int i = 0;
        int j = 0;
        List<int[]> result = new ArrayList<>();
        while (i < firstList.length && j < secondList.length) {
            int a1 = firstList[i][0];
            int a2 = firstList[i][1];

            int b1 = secondList[j][0];
            int b2 = secondList[j][1];

            if (b1 <= a2 && a1 <= b2) {
                result.add(new int[] {Math.max(a1, b1), Math.min(a2, b2)});
            }
            if (b2 > a2) {
                i++;
            } else {
                j++;
            }
        }
        int[][] finalResult = new int[result.size()][2];
        for (int idx = 0; idx < result.size(); idx++) {
            finalResult[idx] = result.get(idx);
        }
        return finalResult;
    }
}
/*
a1---a2
        b1-----b2

          a1----a2   
b1-----b2

b1 > a2 or a1 > b2


so intersection happends:
b1 <= a2 and a1 <= b2

max(a1, b1), min(a2, b2)
a1----a2
  b1----b2

  a1----a2
b1----b2

a1-----a2
 b1---b2

 a1---a2
b1------b2 


b2 > a2
i++
else
j++
*/
```