给定两个由闭区间组成的列表 first 和 second ,其中
,
。表示区间,保证这两个列表内部是不存在交集的,并且是排序之后的。
请找出两个区间列表的交集。
数据范围:区间列表的长度满足
, 区间列表中的值满足
import java.util.*; // 比较优雅 public class Solution { public ArrayList<ArrayList<Integer>> intersectionofintervals (ArrayList<ArrayList<Integer>> first, ArrayList<ArrayList<Integer>> second) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<>(); int m = first.size(), n = second.size(), i = 0, j = 0; while (i < m && j < n) { // 没有交集 (循环至相交) while (i < m && j < n && (first.get(i).get(1) < second.get(j).get(0) || second.get(j).get(1) < first.get(i).get(0))) { if (first.get(i).get(1) < second.get(j).get(0)) i++; else j++; } if (i == m || j == n) break; // 越界 // 取交集 (注意左右边界left、right取法) int left = Math.max(first.get(i).get(0), second.get(j).get(0)); int right = Math.min(first.get(i).get(1), second.get(j).get(1)); res.add(new ArrayList<>(Arrays.asList(left, right))); if (first.get(i).get(1) == right) i++; // 取到右端点了,下一个i if (second.get(j).get(1) == right) j++; // 取到右端点了,下一个j } return res; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param first int整型ArrayList<ArrayList<>> * @param second int整型ArrayList<ArrayList<>> * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> intersectionofintervals(ArrayList<ArrayList<Integer>> first, ArrayList<ArrayList<Integer>> second) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); // write code here int firstIndex = 0; int secondIndex = 0; while (firstIndex < first.size() && secondIndex < second.size()) { Integer firstStart = first.get(firstIndex).get(0); Integer firstEnd = first.get(firstIndex).get(1); Integer secondStart = second.get(secondIndex).get(0); Integer secondEnd = second.get(secondIndex).get(1); if (firstStart > secondEnd) { secondIndex++; } else if (firstEnd < secondStart) { firstIndex++; } else { ArrayList<Integer> temp = new ArrayList<>(); temp.add(Math.max(firstStart, secondStart)); if (firstEnd < secondEnd) { temp.add(firstEnd); firstIndex++; } else { temp.add(secondEnd); secondIndex++; } result.add(temp); } } return result; } }