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

ここで達成できる最高の複雑さは 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 に答える
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

これは、2 つの範囲 (要素のカップルの 2 つの任意のセット) の結合を計算し、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 に答える
0

まず、何を明確にしましょうN- それはセグメントの数ですか?

この場合、常に実行できるとは限りません-すべてのセグメント内の個々の数字の数を単純に出力します-その m を呼び出します-O(m) 時間がかかります。したがって、最速のアルゴリズムは O(m+n) より優れていることはありません。

于 2012-04-19T21:21:58.600 に答える