2

我必须总结这样的间隔：

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

有任何想法吗？谢谢你。

4

4 回答 4

2

如果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

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

于 2012-04-20T06:48:01.583 回答
1

我之前在 OCaml 中做过，代码如下：

let rec calc c l1 l2 =
  match c,l1,l2 with                            
      None, (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 < f2 -> calc (Some (f1,t1)) y1 n2
    | None, n1, (f2,t2) :: y2 -> calc (Some (f2,t2)) n1 y2
    | None, _, _ -> []
    | (Some (fc,tc) as cur), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when t1 <= fc -> calc cur y1 n2
    | (Some (fc,tc) as cur), ((f1,t1) :: y1 as n1), (f2,t2) :: y2 when t2 <= fc -> calc cur n1 y2
    | Some (fc,tc), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 <= tc && t1 > fc -> calc (Some (fc,t1)) y1 n2
    | Some (fc,tc), ((f1,t1) :: y1 as n1), (f2,t2) :: y2 when f2 <= tc && t2 > fc -> calc (Some (fc,t2)) n1 y2
    | Some (fc,tc), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 < f2 -> [fc,tc] @ calc (Some (f1,t1)) y1 n2
    | Some (fc,tc), (t :: e as n1), (f2,t2) :: y2 -> [fc,tc] @ calc (Some (f2,t2)) n1 y2
    | Some (fc,tc), [], (f,t) :: tr when f <= tc && t > tc -> calc (Some (fc,t)) [] tr
    | Some (fc,tc), [], (f,t) :: tr when f <= tc && t <= tc -> calc (Some (fc,tc)) [] tr
    | Some (fc,tc), [], x -> [fc,tc] @ x
    | Some (fc,tc), (f,t) :: tr, [] when f <= tc && t > tc -> calc (Some (fc,t)) tr []
    | Some (fc,tc), (f,t) :: tr, [] when f <= tc && t <= tc -> calc (Some (fc,tc)) tr []
    | Some (fc,tc), x, [] -> [fc,tc] @ x

这计算了两个范围的并集（它们是两个任意元素的集合），它是 O(N+M) （N 和 M 是每个集合中单个间隔的数量）。结果排序。

在此之后，您可以轻松地以线性时间计算列表：

List.fold_left (fun a (f,t) -> for i = f to t do a := !a @ [Int i] done; a) (ref []) range

好的，这是 OCaml，但我已经准备好了，所以它可能对你有用，尤其是在通过删除重叠部分来合并间隔的棘手部分上，因为我花了一些时间来弄清楚算法，但我无法向你描述它在元代码中（从实现中可以看出）。

于 2012-04-19T21:24:20.883 回答
1

我相信您可以在这里实现的最佳复杂度是 O(N*log(N)) 其中 N 是间隔数。解决方案并不难——您需要首先按间隔对间隔进行排序，然后再进行一次线性传递来计算它们的并集。我将尝试用 C++ 编写一些代码：

struct Interval {
  int from, to;
  bool operator<(const Interval& other) const {
    if(from != other.from) {
      return from < other.from;
    }
    return to < other.to;
  }
};

int main() {
  vector<Interval> intervals;
  sort(intervals.begin(), intervals.end());

  int current_position = intervals[0].from;
  int sum = 0;
  for (int i = 0; i < intervals.size(); ++i) {
    if (intervals[i].to < current_position) {
      continue;
    } else if (intervals[i].from <= current_position) {
      sum += intervals[i].to - current_position + 1;
      current_position = intervals[i].to + 1;
    } else {
      sum += intervals[i].to - intervals[i].from + 1;
      current_position = intervals[i].to + 1;
    }
  }
  std::cout << sum << std::endl;
  return 0;
}
于 2012-04-20T06:24:47.987 回答
0

首先，让我们弄清楚什么N是 - 是段数吗？

如果是这种情况，那么您不能总是这样做 - 只需打印出所有段中的单个数字的数量 - 称之为 m - 需要 O(m) 时间。那么，最快的算法不会比 O(m+n) 更好

于 2012-04-19T21:21:58.600 回答