# 关于时间区间分割算法问题

kute
• 491

1-9：表示 1号到9号

## 例子1：

1-8、9-9、10-19、20-29、30-31

## 例子2：

1-3、4-8、9-9、10-19、20-28、29-29、30-31

1-9、10-29、30-31

## 例子3：

1-7、8-8、9-9、10-19、20-29、30-31

4 个回答
Mannix
• 1.2k

\$\$ 1-9、10-29、30-31 \Rightarrow 1、10、30、32 \$\$

``````const minusAndIntersect = (A, B) => {
const R = []
if (A.length == 0) return R
let iB = 0
while (iB < B.length && B[iB] <= A[0]) ++iB
R.push(A[0])
for (let iA = 1; iA < A.length; ++iA) {
while (iB < B.length && B[iB] <= A[iA]) R.push(B[iB++])
if (A[iA] > R.at(-1)) R.push(A[iA])
}
return R
}

const A = [1, 10, 30, 32]
console.log(minusAndIntersect(A, [1, 9, 20, 32])) // [1, 9, 10, 20, 30, 32]
console.log(minusAndIntersect(A, [4, 9, 20, 29])) // [1, 4, 9, 10, 20, 29, 30, 32]
console.log(minusAndIntersect(A, [8, 9, 20, 32])) // [1, 8, 9, 10, 20, 30, 32]``````

``````const minusAndIntersect = (A, B) => {
const R = []
if (A.length == 0) return R
B = B.flat()
for (let i = 1; i < B.length; i += 2) ++B[i]
let iB = 0
for (const a of A) {
let [begin, end] = a
while (iB < B.length && B[iB] <= begin) ++iB
while (iB < B.length && B[iB] <= end) {
if (B[iB] > begin) {
R.push([begin, B[iB] - 1])
begin = B[iB]
}
++iB
}
R.push([begin, end])
}
return R
}

const A = [[1, 9], [10, 29], [30, 31]]
console.log(minusAndIntersect(A, [[1, 8], [9, 19], [20, 31]])) // [[1,8],[9,9],[10,19],[20,29],[30,31]]
console.log(minusAndIntersect(A, [[4, 8], [9, 19], [20, 28]])) // [[1,3],[4,8],[9,9],[10,19],[20,28],[29,29],[30,31]]
console.log(minusAndIntersect(A, [[8, 8], [9, 19], [20, 31]])) // [[1,7],[8,8],[9,9],[10,19],[20,29],[30,31]]
// 前后区间不紧贴的例子
console.log(minusAndIntersect([[1, 10], [21, 30]], [[6, 25]])) // [[1,5],[6,10],[21,25],[26,30]]``````

``````public static void main(String[] args) {
MinusAndIntersect f = new MinusAndIntersect(ranges(1, 9, 10, 29, 30, 31));
System.out.println(f.exec(ranges(1, 8, 9, 19, 20, 31)));
System.out.println(f.exec(ranges(4, 8, 9, 19, 20, 28)));
System.out.println(f.exec(ranges(8, 8, 9, 19, 20, 31)));
// 前后区间不紧贴的例子
System.out.println(new MinusAndIntersect(ranges(1, 10, 21, 30)).exec(ranges(6, 25)));
/*
[1-8, 9-9, 10-19, 20-29, 30-31]
[1-3, 4-8, 9-9, 10-19, 20-28, 29-29, 30-31]
[1-7, 8-8, 9-9, 10-19, 20-29, 30-31]
[1-5, 6-10, 21-25, 26-30]
*/
}

static List<Range> ranges(int... beginAndEnd) {
int n = beginAndEnd.length;
List<Range> ranges = new ArrayList<>(n >>> 1);
for (int i = 0; i < n; ranges.add(new Range(beginAndEnd[i++], beginAndEnd[i++])));
return ranges;
}

static class Range {

int begin, end;

Range(int beginInclusive, int endInclusive) {
begin = beginInclusive;
end = endInclusive;
}

@Override
public String toString() {
return begin + "-" + end;
}

}

static class MinusAndIntersect {

Range[] A;
List<Range> R;
int i = -1, begin, end;

MinusAndIntersect(List<Range> A) {
this.A = A.toArray(new Range[A.size()]);
}

List<Range> exec(List<Range> B) {
R = new ArrayList<>();
if (next()) {
for (Range b : B)
if (!addUntil(b.begin - 1) || !addUntil(b.end)) return R;
}
return R;
}

boolean addUntil(int last) {
while (begin <= last) {
if (end <= last) {
if (!next()) return false;
} else {
begin = last + 1;
break;
}
}
return true;
}

boolean next() {
if (++i == A.length) {
i = -1;
return false;
}
Range a = A[i];
begin = a.begin;
end = a.end;
return true;
}

}``````