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.

现在,我不得不在奥(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
", 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) 。

但是,如果我们重新愿意面对这一点,第一步是按其左手价值来划分间隔。 (时间O(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

(该法典是间隔数的直线,非线性碎片正在分类中)。)

Answer 2

此前,我曾在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,但我准备这样做,或许会有助于你,特别是在通过删除重叠部分合并间隔的trick缩部分上,因为我花了一段时间来估算算法,但我无法在星码中向你们描述(正如你从执行中看到的那样)。

Answer 3

我认为,你在此所能达到的最复杂程度是O(N*log(N)),N是间隔时间。解决办法并不十分困难——你们需要先在开始之前对间隔进行分类,然后通过另一条直线手段来补偿他们的工会。我将努力在++中撰写一些法典:

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;
}

Answer 4

First, let s be clear about what N is - is it the number of segments?

如果是这样的话,那么你总是能够这样做——简单地列举所有各行各业的个别数字——即:m——需要O(m)时间。那么,最快的算法可能比O(m+n)好。

友情链接