algorithm - 查找两个整数区间之间的差集

Question

我最近遇到了一个问题。我必须找到两个整数区间之间的差值。间隔由两个边界决定 - 高和低。不包括高点的地方。

好吧，我想出了解决方案，要考虑几种情况。一下子就变成了 12 例。我在下面列出了其中一些。看起来很奇怪。有更简单的解决方案吗？

        //a[  a) b[  b) 
        // [   )  
        if (a._end <= b._start)
            return Lst(a);

        //a[  b[  a)  b)
        // [   )
        if (a._start < b._start && b._start < a._end &&
            b._start < a._end && a._end < b._end)
            return Lst(Rng(a.Start(), b.Start()));

        //b[  a[  b)  a)
        //         [   )
        if (b._start < a._start && a._start < b._end &&
            a._start < b._end && b._end < a._end)
            return Lst(Rng(b.End(), a.End()));

        //b[  b) a[  a)  
        //        [   )
        if (b._end <= a._start)
            return Lst(a);

        //a[  b[  b)  a)
        // [   )   [   )
        if (a._start < b._start && b._start < a._end &&
            a._start < b._end && b._end < a._end)
            return Lst(
                Rng(a.Start(), b.Start()),
                Rng(b.End(), a.End()));

Answer 1

(我不明白你为什么决定生成像 ... b._start < a._end && b._start < a._end ... 这样的冗余条件)

除其他事项外，由于您尝试在单个 return 语句中构建整个结果，因此您的代码变得更加复杂。如果您可以在局部变量中增量构建结果，然后返回该局部变量，代码将大大简化。

依赖标准函数，如 min和 max而不是嵌入 min/max代码中的逻辑也会使其更加紧凑。

假设我们在本地列表变量 result 中构建结果并通过执行 result.append() 向其附加间隔.

差异操作最多可以产生两个区间:一个在b 的左边。 , 另一个在 b 的右边.让我们按顺序计算它们

List result;

if (a._start < b._start)
  // Left portion exists
  result.append(Rng(a._start, min(a._end, b_start)));

if (a._end > b._end)
  // Right portion exists
  result.append(Rng(max(a._start, b._end), a._end));
  
return result;

我假设间隔已经标准化，即 a._start <= a._end ，但您的代码似乎也依赖于该假设。