给定两个区间 A = [1, 10] 和 B = [3, 7]。返回所有非重叠区间,因此结果将是 [1, 2] 和 [8, 10]
假设 A 和 B 之间始终存在重叠。
我试着把问题分成几个案例: 假设你想找到 A 和 B 之间的非重叠区间。
Case 1:
A = [0, 5] and B = [2, 3].
The result would be [0, 1] and [4, 5].
General case:
if A[0] < B[0] and B[1] < A[1]
then [A[0], B[0] - 1] and [B[1] + 1, A[1]]
Case 2:
A = [0, 5] and B = [0, 5].
The result would be [].
General case:
if A[0] == B[0] and B[1] == A[1]
then []
.
.
.
我继续制作另外 4 个案例。但这似乎有点太乏味了。有没有更简单的实现方式?
谢谢
最佳答案
据我正确理解,输入将包含两个区间,例如 A
和 B
,我们必须找到两个区间不共享的所有线性子段。
我们可能会观察到最多 2
间隔作为解决方案。我们可以通过检查以下条件来打印解决方案:
if (A[0] > B[1] || B[0] > A[1]) { // for non-intersecting independent intervals
print: {A[0], A[1]} and {B[0], B[1]}
} else {
if (A[0] != B[0]) {
print: {min(A[0], B[0]), max(A[0], B[0]) - 1}
}
if (A[1] != B[1]) {
print: {min(A[1], B[1]) + 1, max(A[1], B[1])}
}
}
关于arrays - 给定两个区间找到所有不重叠的区间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56446230/