Дан набор интервалов, представляющий из себя массив пар чисел: начало и конец интервала
intervals[i] = [start_i, end_i]
Нужно слить все пересекающиеся интервалы и вернуть такой набор, в котором все интервалы непересекаются, и их объединение покрывает все интервалы из исходного набора.
Пример
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Решение:
Метод сканирующей прямой
Во вспомогательном массиве сохраним индексы и тип события (интервал открылся 1, закрылся -1) и отсортируем
Далее пройдемся по всем событиям в порядке индексов и будем поддерживать счетчик количества интервалов, которые покрывают текущую точку. Если в какой-то момент счетчик становится 0, то добавляем в ответ новый интервал и идем дальше. Если ненулевой, то ничего добавлять не нужно
static bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first != b.first)
return a.first < b.first;
return a.second > b.second;
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = (int)intervals.size();
vector<pair<int, int>> ev;
for (int i = 0; i < n; ++i) {
ev.emplace_back(intervals[i][0], 1);
ev.emplace_back(intervals[i][1], -1);
}
sort(ev.begin(), ev.end(), cmp);
vector<vector<int>> res;
int cnt = 0, first = -1;
for (auto event : ev) {
int ind = event.first, type = event.second;
cnt += type;
if (cnt == 0) {
res.push_back({first, ind});
first = -1;
} else if (first == -1)
first = ind;
}
return res;
}
@algoses