将整数与范围匹配

Question

我有 n 个整数和 m 个范围（认为 [a, b]）的数字 n <= m。如果整数在范围内，即 a <= integer <= b，则可以匹配整数和范围。一个范围只能匹配一个整数，反之亦然。

这是一个例子：

范围： [0, 5], [3, 6], [9, 21]

整数: 1, 5

最大有效匹配是将 1 匹配到第一个范围，将 5 匹配到第二个范围。

我想找到一个最大化匹配整数个数的贪心算法。我最初的想法是贪婪地选择最短的范围并匹配最接近最短范围起点的数字（因此范围[a, b]中的a）。但是，我不确定这是对的。

Answer 1

这里有一个想法：当一个间隔结束时，您不能在该间隔中放置一个大于结束的整数。这意味着如果您打算尽可能多地填充，则需要首先满足较早结束的范围。现在，如果两个区间的两端相等，你会怎么做？你填满那个开始得更快的。通过这种方式，您可以增加以相同结尾但开始较晚的下一个 range/interval 填满的机会。

现在，假设我们对整数 none-decreasing 和区间进行排序，先到尾再开始，none-decreasing 并开始贪婪地填充区间。可能发生的情况是一个区间落在区间数组的末尾，因为它有一个大的末端，而它有一个非常小的开始。当我们遍历整数时，如果因为第一个区间的开始大于那个整数而跳过一个整数，我们运行有忽略它的风险，而我们可以在后面的区间中用大端拟合整数和非常小的开始。

为了减轻这种情况，我们需要检查我们考虑的每个整数的所有剩余间隔，并取第一个我们可以适合整数的间隔（如果有的话）。这将我们的运行时间复杂度恶化为 O(n * m)，但我不明白我们如何克服它以使其成为线性的。

这里将上面的想法转换成算法：

将您的 ranges/intervals 排序到末尾，然后从 none-decreasing 开始排序。
对整数进行排序 none-decreasing。
设置一组记录使用的间隔，used_intervals。
为生成的整数创建一个数组，res。
运行下面的嵌套循环：

for integer in integers:
  for interval in intervals:
    if interval in used_intervals: continue
    if interval.start <= integer <= interval.end:
      res.push(integer)
      used_intervals.add(interval)

时间复杂度分析：

间隔排序是 O(m * log m) 其中 m 是间隔数
整数排序是O(n * log n)，其中n是整数的个数
嵌套循环是O(m * n) 由于 n <= m，这将大 O 的时间复杂度降低到 O(max(m * n, m * log m))。

Space复杂度分析： O(m)，排序，结果数组，集合

我不确定我们是否可以优化这个，不是时间复杂度而是优化。感谢任何反馈。

Answer 2

如果您匹配所有可能的匹配项，允许多个连接，会怎样w.r.t。整数，并在参与多个连接时消除先前的匹配项 w.r.t。范围？您必须通过删除任何剩余的倍数来跟进以获得有效结果。

在您的示例中，您将遍历整数：

1 : match [0,5]
5 : match [0,5], [3,6] then eliminate [0,5]

稍微复杂一点的示例可能是 1、5、7，范围为 [0,5]、[2,6]、[3,10]、[5,21]

1 : match [0,5]
5 : match [0,5], [2,6], [3,10], [5,21] then eliminate [0,5]
7 : match [3,10], [5,21] then eliminate [3,10]

你还剩下：

1 : [0,5]
5 : [2,6], [3,10], [5,21]
7 : [5,21]

您优先从 5 中消去 [5,21]，因为该范围有多个位置，并且您要从一个具有多个位置的整数中消去。最后，您消除 [3,10]（尽管您可以消除 [2,6]）以消除整数中的所有倍数。

将整数与范围匹配

Matching integers to ranges

algorithm

greedy