非重叠区间PAIRS的组合

Question

我最近做了一项编码挑战，我的任务是返回在给定一个列表中的起点和一个列表中的终点时不重叠的唯一间隔对的数量。我能够提出一个 n^2 解决方案，并通过使用一组对 (start, end) 的每个条目元组进行散列来消除重复项。我想知道是否有更有效的方法来解决这个问题，或者这是我能做的最好的方法：

def paperCuttings(starting, ending):
    # Pair each start with its corresponding end and sort
    intervals = sorted(zip(starting, ending), key=lambda x: x[1])
    non_overlaps = set()

    print(intervals)

    # Store valid combinations
    for i in range(len(intervals)):
        for j in range(i+1, len(intervals)):
            # If the ending of the first is less than the starting of the second, they do not overlap
            if intervals[i][1] < intervals[j][0]:                
                non_overlaps.add((intervals[i], intervals[j]))

    return len(non_overlaps)

starting = [1,1,6,7]
ending = [5,3,8,10]
print(paperCuttings(starting, ending)) # should return 4

starting2 = [3,1,2,8,8]
ending2 = [5, 3, 7, 10, 10]
print(paperCuttings(starting2, ending2))  # should return 3

我问是因为我在一些隐藏的测试用例中超时了

Answer 1

这是 Ruby 中的解决方案。通过解释，我将提供代码到 Python 的转换应该很简单。

我假设非重叠区间没有共同点，甚至没有端点¹。

def paperCuttings(starting, ending)
  # compute an array of unique intervals sorted by the beginning of each interval
  intervals = starting.zip(ending).uniq.sort

  n = intervals.size
  count = 0

  # loop over the indices of all but the last interval.
  # the interval at index i of intervals will be referred to below as interval i 
  (0..n-2).each do |i|
    # intervals[i] is interval i. It is array containing its two endpoints
    # extract the second endpoint to the variable endpoint
    _, endpoint = intervals[i]
     
    # find the index of the first interval j > i for which 
    # intervals[j].first > endpoint, where intervals[j].first is
    # the beginning of interval j
    k = (i+1..n-1).find { |j| intervals[j].first > endpoint }

    # k = nil if no such interval is found, in which case continue with
    # the next interval i
    next if k == nil

    # As intervals i and k are non-overlapping, interval i is non-overlapping
    # with all intervals l, k <= l <= n-1, of which there are n-k, so
    # that is added to count
    count = count + n - k
  end
  # return count
  count
end

---

尝试一下。

starting = [1, 1, 6,  7]
ending   = [5, 3, 8, 10]

paperCuttings(starting, ending)
  #=> 4

starting = [3, 1, 2,  8,  8]
ending   = [5, 3, 7, 10, 10]
paperCuttings(starting, ending)
  #=> 3

---

这里我解释一下计算过程

intervals = starting.zip(ending).uniq.sort

对于

starting = [3, 1, 2,  8,  8]
ending   = [5, 3, 7, 10, 10]

a = starting.zip(ending)
  #=> [[3, 5], [1, 3], [2, 7], [8, 10], [8, 10]]
b = a.uniq
  #=> [[3, 5], [1, 3], [2, 7], [8, 10]]
b.sort
  #=> [[1, 3], [2, 7], [3, 5], [8, 10]]

问题陈述要求删除重复项。

b

的元素按其第一个元素排序。如果有两个数组具有相同的第一个元素，则第二个元素将用作决胜局，尽管这在这里并不重要。

^{1。如果仅共享一个端点的间隔被视为重叠，请将}

starting[j] >= endpoint

更改为

starting[j] > endpoint

。