algorithm - 将整数与范围匹配

Question

我有n整数和 m范围(想想 [a, b] )这样的数字 n <= m .如果整数在范围内，则可以匹配整数和范围，即 a <= integer <= b .一个范围只能与一个整数匹配，反之亦然。

这是一个例子:

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

整数:1、5

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

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

Answer 1

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

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

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

下面是将上述想法转化为算法:

1. 按末尾对范围/间隔进行排序，然后开始不递减。
2. 对整数进行非递减排序。
3. 设置一组记录使用的间隔，used_intervals .
4. 有一个结果整数数组，res .
5. 运行以下嵌套循环:

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 ，这将 Big O 的时间复杂度降低到 O(max(m * n, m * log m)) .

空间复杂度分析: O(m) ,排序,结果数组,集合

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