algorithm - 求和间隔

Question

我必须像这样对间隔求和:

1..6
2..4
The result is 1..6, so there are 6 numbers in the end.

这是另一个例子:

4..6
8..10
14..16
4, 5, 6, 8, 9, 10, 14, 15, 16, the size is 9.

现在，我必须在 O(N) 中执行此操作。这是我使用 STL 很快想出的一个不太好的方法:

#include <set>
#include <stdio.h>

using namespace std;

int main() {
  int n;
  scanf("%d", &n);

  set<int> numbers;
  int a, b;
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a, &b);
    for (int u = a; u <= b; u++) {
      numbers.insert(u);
    }
  }

  printf("%d\n", numbers.size());

  return 0;
}

知道如何在 O(N) 中完成这项工作吗？我知道我之前必须对它进行排序，但我可以使用我刚制作的这个:

bool compare(const vector<int> first, const vector<int> second) {
  if (first[0] == second[0]) return first[1] < second[1];
  return first[0] < second[0];
}

sort(intervals.begin(), intervals.end(), compare);

所以它是 O(log N + N)。

有什么想法吗？谢谢。

Answer 1

如果 n 是间隔数，那么我认为没有办法做到这一点不是 O(n log(n))。

但如果我们愿意面对这个问题，第一步就是按照区间的左侧值对区间进行排序。 (这需要时间 O(n log(n))。)然后您尝试根据以下伪代码计算并集中的最小区间集

answer = 0
while intervals left
    (min, max) = next interval
    while intervals left and min of next interval < max:
        if max < max of next interval:
            max = max of next interval
        move forward in interval list
    # the next interval is [min..max]
    answer += max - min + 1

(这段代码在区间数上是线性的，非线性的那 block 在对它进行排序。)