интервалы Подведение

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. 

Теперь я должен сделать это в 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 (N журнал + N).

Любые идеи? Спасибо.

Answer 1

Во-первых, давайте поясним, что такое N - это количество сегментов?

Если это так, то вы не всегда можете это сделать - просто распечатайте количество отдельных номеров во всех сегментах - вызовите, что m - принимает время O (m). Самый быстрый алгоритм, то не может быть лучше, чем O (т + п)

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, но у меня было готово, так может быть, это будет полезно для вас, особенно хитрой части, переходящей интервалы по удаляя перекрывающиеся части, поскольку я потратил некоторое время на то, чтобы выяснить алгоритм, но я не мог описать его вам в метакоде (как вы можете видеть из реализации).

Answer 3

Я считаю, что наилучшей сложности, которую вы можете достичь здесь, является 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; 
} 

Answer 4

Если 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 

(Этот кодом является линейным по числу интервалов, нелинейная часть сортирует его.)