使操作有效的唯一方法是保持区间列表排序和不重叠（这可以在O(n log n)中完成）。[参见下面的注解]。
在两个列表都已排序且不重叠的情况下，任何集合操作（并集、交集、差集、对称差集）都可以通过简单的合并来执行。
合并操作很简单：同时按顺序遍历两个参数的端点。（注意，每个区间列表的端点都是排序的，因为我们要求区间不重叠。）对于发现的每个端点，判断它是否在结果中。如果结果当前有奇数个端点，并且新的端点不在结果中，则将其添加到结果中;类似地，如果结果当前具有偶数个端点并且新端点在结果中，则将其添加到结果中。在此操作结束时，结果是端点列表，在间隔开始和间隔结束之间交替。
在Python中是这样的：

# In all of the following, the list of intervals must be sorted and 
# non-overlapping. We also assume that the intervals are half-open, so
# that x is in tp(start, end) iff start <= x and x < end.

def flatten(list_of_tps):
    """Convert a list of intervals to a list of endpoints"""
    return reduce(lambda ls, ival: ls + [ival.start, ival.end],
                  list_of_tps, [])
    
def unflatten(list_of_endpoints):
    """Convert a list of endpoints, with an optional terminating sentinel,
       into a list of intervals"""
    return [tp(list_of_endpoints[i], list_of_endpoints[i + 1])
            for i in range(0, len(list_of_endpoints) - 1, 2)]
    
def merge(a_tps, b_tps, op):
    """Merge two lists of intervals according to the boolean function op"""
    a_endpoints = flatten(a_tps)
    b_endpoints = flatten(b_tps)
    
    sentinel = max(a_endpoints[-1], b_endpoints[-1]) + 1
    a_endpoints += [sentinel]
    b_endpoints += [sentinel]
    
    a_index = 0
    b_index = 0
    
    res = []
    
    scan = min(a_endpoints[0], b_endpoints[0])
    while scan < sentinel:
        in_a = not ((scan < a_endpoints[a_index]) ^ (a_index % 2))
        in_b = not ((scan < b_endpoints[b_index]) ^ (b_index % 2))
        in_res = op(in_a, in_b)
        
        if in_res ^ (len(res) % 2): res += [scan]
        if scan == a_endpoints[a_index]: a_index += 1
        if scan == b_endpoints[b_index]: b_index += 1
        scan = min(a_endpoints[a_index], b_endpoints[b_index])
    
    return unflatten(res)

def interval_diff(a, b):
    return merge(a, b, lambda in_a, in_b: in_a and not in_b)

def interval_union(a, b):
    return merge(a, b, lambda in_a, in_b: in_a or in_b)

def interval_intersect(a, b):
    return merge(a, b, lambda in_a, in_b: in_a and in_b)

注意事项

1.间隔[a, b)和[b, c)不重叠，因为它们不相交;b只属于第二个。这两个区间的并集仍然是[a,c)。但是为了这个答案中的函数的目的，最好也要求区间不相邻，通过扩展“不重叠”的定义来包括区间相邻的情况;否则，我们会冒着发现输出中不必要地包含了邻接点的风险。（严格地说，这并不是错误的，但是如果输出是确定性的，那么测试函数就更容易了。）
下面是一个函数的示例实现，该函数将任意的区间列表规范化为一个排序的、不重叠的区间。

def interval_normalise(a):
    rv = sorted(a, key = lambda x: x.start)
    out = 0
    for scan in range(1, len(rv)):
        if rv[scan].start > rv[out].end:
            if rv[out].end > rv[out].start: out += 1
            rv[out] = rv[scan]
        elif rv[scan].end > rv[out].end:
            rv[out] = tp(rv[out].start, rv[scan].end)
    if rv and rv[out].end > rv[out].start: out += 1
    return rv[:out]

这个问题可以用扫描线算法来解决。其思想是将两个集合中的区间的所有起点保存在一个有序数组中，并将终点保存在另一个有序数组中，用它们属于哪个集合的信息来标记它们。

A              B
[(1, 4), (7, 9)] - [(3,5)]
A: start:[1,7] end:[4,9], B: start:[3]end:[5]
start:[(1,a),(3,b),(7,a)]
end: [(4,a),(5,b),(9,a)]

现在有两个指针，一个指向每个数组的开头。在循环中，递增一个指向最小值的指针，添加从a开始直到以b或a结束的间隔。例如，对于上面的内容，我们将按此顺序迭代点

(1,a) (3,b) (4,a) (5,b) (7,a) (9,a)
# and adding intervals where we have seen an start a and an end a or b
(1,3) (7,9)

这导致在区间数方面的线性解。

另一个使用numpy的实现。我假设，因为我认为使用 integer endpoints 更自然，区间是封闭的。对于我下面建议的方法，我们绝对需要照顾（半封闭）区间，包括-infinity和+infinity。

def merge_intervals(intervals):
    # Normalize to sorted non-overlaping intervals. Aimilar idea as in
    # https://www.geeksforgeeks.org/merging-intervals/
    if len(intervals)==0: return intervals 
    assert np.all(intervals[:,0]<=intervals[:,1]), f"merge_intervals: intervals not well defined. intervals={intervals}"
    if len(intervals)==1: return intervals    
    intervals = np.sort(intervals.copy(),axis=0)
    stack = []
    # insert first interval into stack
    stack.append(intervals[0])
    for i in intervals[1:]:
        # Check for overlapping interval,
        # if interval overlap
        if i[0] > stack[-1][1]+1:
            stack.append(i)
        else:
            stack[-1][1] = max(stack[-1][1], i[1])
    return np.array(stack)

def union_intervals(a,b):
    return merge_intervals(np.r_[a,b])

# The folowing is the key function. Needs to work  
# well with infinities and empty sets.
def complement_intervals(a): 
    if len(a)==0: return np.array([[-np.inf,np.inf]])
    a_normalized = merge_intervals(a)
    result0 = np.r_[-np.inf,a_normalized[:,1]+1]
    result1 = np.r_[a_normalized[:,0]-1,np.inf] 
    non_empty = np.logical_and(result0 < np.inf, result1 > -np.inf)
    result = np.c_[result0[non_empty],result1[non_empty]]
    if np.array_equal(result,np.array([[np.inf,-np.inf]])):
        result = np.array([])
    return merge_intervals(result)

def intersection_intervals(a,b):
    union_of_complements = union_intervals(complement_intervals(a),complement_intervals(b))
    return  complement_intervals(union_of_complements)

def difference_intervals(a,b):
    return intersection_intervals(a,complement_intervals(b))