Найти охват набора интервалов

Question

Я столкнулся с этим вопросом во время подготовки к интервью долго назад и подумал, что это интересная проблема для решения. Проблема заключается в следующем: Найдите покрытие набора интервалов Например - [1,4], [-2,3), [9,10]: выход должен быть 7 (набор интервалов - 2, -1,0,1,2,3,9).

Мой первоначальный подход состоял в том, чтобы перебирать множество интервалов; добавьте число в каждом интервале в список Sorted Linked. Если какой-либо номер уже существует в отсортированном списке, пропустите его. Я считаю, что это занимает время O (N^2) и потребляет пространство O (N), поэтому мы, вероятно, могли бы сделать лучше.

В качестве альтернативы мы можем использовать Interval BST. Однако это, по-видимому, в основном используется для выяснения, существует ли перекрытие с заданным интервалом (который принимает O (lgn)). Обнаружение его охвата, похоже, снова примет O (n^2). Можем ли мы лучше, чем O (n^2)?

Answer 1

Вы можете посмотреть на них как на пары и отсортировать их по первому элементу.

После сортировки вы будете иметь: {< -2, 2>, < 1,3>, < 9, 9>}.

Сортировка займет O (NlogN).

Теперь сделайте переменную сумму = 0.

Затем установите L = (1) .left и R = (1) .right.

Линейно перемещайте все, соблюдая самый большой R, с которым вы столкнулись, до тех пор, пока R < (k) .left, а затем выполните сумму + = abs (L - R) + 1 и продолжайте движение как описано. Это займет около O (N). Итак, в целом: O (NlogN + N) ~ O (NlogN).

Пространство также линейно.

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <climits> 

using namespace std; 
typedef pair<int, int> pii; 

int main() { 
    int l, r; 
    vector<pii> pairs; 
    while (cin >> l >> r) { 
     pairs.emplace_back(l, r); 
    } 
    pairs.emplace_back(INT_MAX, INT_MAX); // sentinel 
    sort(pairs.begin(), pairs.end(), 
    [](const pii& x, const pii& y) { return x.first < y.first; }); 

    auto p_one = pairs.begin(), p_two = pairs.begin() + 1; 
    int L = p_one->first; 
    int R = p_one->second; 
    int sum = 0; 
    while (p_two != pairs.end()) { 
     if (R < p_two->first) { 
      sum += abs(L - R) + 1; 
      L = p_two->first; 
      R = INT_MIN; 
     } 
     p_one++; p_two++; 
     if (p_one->second > R) R = p_one->second; 
    } 
    cout << sum; 
} 

P.S. Я не полностью тестировал код, но, похоже, он работает.