总结间隔 [英] Summing intervals

问题描述

我要总结的间隔像这样的：

I have to sum intervals like these:

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：

Now, I have to do this in O(N). Here's a not-so-good approach I quickly came up with using the 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）来完成？我知道我之前对它进行排序，但我可以用这个，我只是做：

Any idea of how this can be done in O(N)? I know I have to sort it before, but I can use this I just made:

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

So it'd be O(log N + N).

任何想法？谢谢你。

推荐答案

如果 N 的间隔数话，我不认为有一种方法可以做到这不是 O（N日志（N））。

If n is the number of intervals then I don't think that there is a way to do this that is not O(n log(n)).

但是，如果我们愿意面对的是，第一个步骤是通过左边的值的时间间隔进行排序。 （这需要时间 O（N日志（N）））。然后尝试根据以下伪code来计算一组间隔最少在工会

But if we're willing to face that, the first step is to sort the intervals by their left-hand value. (This takes time O(n log(n)).) Then you try to compute a minimal set of intervals in the union according to the following pseudo-code

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

（此code是线性的间隔的数量，非线性片排序的。）

(This code is linear in the number of intervals, the non-linear piece is sorting it.)

这篇关于总结间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！