Interval List Intersections
发布时间：2020-12-13 22:37:20 所属栏目：Linux 来源：网络整理
导读：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
|
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? ? Example 1:
Input: A = [[0,2],[5,10],[13,23],[24,25]],B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,25]] Reminder: The inputs and the desired output are lists of Interval?objects,and not arrays or lists. 1 class Solution { 2 public int[][] intervalIntersection(int[][] A,int[][] B) { 3 if (A == null || A.length == 0 || B == null || B.length == 0) { 4 return new int[0][0]; 5 } 6 7 int m = A.length,n = B.length; 8 int i = 0,j = 0; 9 List<int[]> res = new ArrayList<>(); 10 while (i < m && j < n) { 11 int[] a = A[i]; 12 int[] b = B[j]; 13 14 // find the overlap... if there is any... 15 int startMax = Math.max(a[0],b[0]); 16 int endMin = Math.min(a[1],b[1]); 17 18 if (endMin >= startMax) { 19 res.add(new int[]{startMax,endMin}); 20 } 21 22 //update the pointer with smaller end value... 23 if (a[1] == endMin) { i++; } 24 if (b[1] == endMin) { j++; } 25 } 26 return res.toArray(new int[0][0]); 27 } 28 } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
