Java是一种面向对象的编程语言,它可以轻松地实现求区间的交集和并集。区间交集和并集是计算机科学中的一种重要问题,通常用来解决有关时间、距离、空间等方面的问题。
下面是Java中实现求区间交集和并集的代码。
public class Interval {public int start;public int end;public Interval() {start = 0;end = 0;}public Interval(int s, int e) {start = s;end = e;}}public class Solution {public ListintervalIntersection(List A, List B) {int i = 0, j = 0;List res = new ArrayList<>();while (i< A.size() && j< B.size()) {Interval a = A.get(i), b = B.get(j);int startMax = Math.max(a.start, b.start);int endMin = Math.min(a.end, b.end);if (startMax<= endMin) {res.add(new Interval(startMax, endMin));}if (a.end< b.end) {i++;} else {j++;}}return res;}public List intervalUnion(List A, List B) {List res = new ArrayList<>();A.addAll(B);Collections.sort(A, (o1, o2) ->o1.start - o2.start);int i = 0;while (i< A.size()) {int start = A.get(i).start;int end = A.get(i).end;while (i + 1< A.size() && end >= A.get(i + 1).start) {end = Math.max(end, A.get(i + 1).end);i++;}res.add(new Interval(start, end));i++;}return res;}}
以上代码中,intervalIntersection方法用于求区间的交集,而intervalUnion方法用于求区间的并集。这两个方法接收两个参数,分别代表要求交集和并集的两个区间列表。
在intervalIntersection方法中,我们使用双指针来遍历两个区间列表,并计算区间的交集。具体来说,我们维护两个指针i和j,分别指向列表A和B中的区间。然后,我们比较A[i]和B[j]的起点和终点,并计算它们的交集。如果交集存在,就将其加入到结果列表中。最后,我们移动指针i或j,使其指向下一个区间。而在intervalUnion方法中,我们首先将两个区间列表合并成一个列表。然后,我们对该列表按照起点进行排序。接下来,我们维护一个指针i,用于遍历该列表,并计算区间的并集。具体来说,我们从第一个区间开始,依次计算它和后面各个区间的并集,直到找到一个没有重叠的区间为止。然后,我们将计算出的区间加入到结果列表中。最后,我们移动指针i,重复以上步骤直至所有区间都被遍历完毕。