求和间隔

我必须对这样的间隔进行求和：

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)。

有任何想法吗？谢谢。

If 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

（这段代码在间隔数量上是线性的，非线性部分正在对其进行排序。）