986. Interval List Intersections

Problem Statement

Pattern: Related: 919 · Meeting Rooms II

---

Solution

public int[][] intervalIntersection(int[][] A, int[][] B) {
	List<int[]> res = new ArrayList<>();
	
	for (int i = 0, j = 0; i < A.length && j < B.length;) {
		// find the closest start and end points of both intervals
		int start = Math.max(A[i][0], B[j][0]);
		int end = Math.min(A[i][1], B[j][1]);
		
		// if overlap add to res
		if(start <= end) res.add(new int[] {start, end});
		
		// increment arr w the laggin interval
		if(A[i][1] < B[j][1]) i++;
		else j++;
	}
	
	return res.toArray(new int[res.size()][2]);
}

Notes

• [Python] Two Pointer Approach + Thinking Process Diagrams - LeetCode Discuss
• As clear as can be explained 👆

This can also be solved using the pointer logic / Line Sweep Algorithm approaach from 919 · Meeting Rooms II

public int[][] intervalIntersection1(int[][] firstList, int[][] secondList) {
	// create start and end arrays
	int n1 = firstList.length, n2 = secondList.length;
	int[] start = new int[n1 + n2], end = new int[n1 + n2];
	
	for (int i = 0; i < n1; i++) {
		start[i] = firstList[i][0];
		end[i] = firstList[i][1];
	}
	for (int i = 0; i < n2; i++) {
		start[i + n1] = secondList[i][0];
		end[i + n1] = secondList[i][1];
	}
	
	Arrays.sort(start);
	Arrays.sort(end);
	
	// find start value and end value of overlapping intervals
	int s = 0, e = 0, sim = 0, sval = -1;
	ArrayList<int[]> res = new ArrayList<>();
	while (e < end.length) {
		// start pointer
		if (s < start.length && start[s] <= end[e]) {
			if (++sim == 2) sval = start[s];
			s++;
		}
		// end pointer
		else {
			if (--sim == 1) res.add(new int[]{sval, end[e]});
			e++;
		}
	}
	return res.toArray(new int[0][]);
}

like so 👆. but this is unnecassary since 2 intervals within the each given array A[] or B[] will never overlap

Each list of intervals is pairwise disjoint and in sorted order.

If they were’nt however, the above approach would be necessary