Написано: 16.03.2023
56. Объединить интервалы (Merge Intervals)
Задание.
Получен массив intervals, где intervals[i] = [starti, endi]
Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые охватывают все интервалы во входных данных.
Пример 1.
Входные данные: intervals = [ [1,3], [2,6], [8,10], [15,18] ]
Результат: [ [1,6], [8,10], [15,18] ]
Пояснение: Поскольку интервалы [1,3] и [2,6] перекрываются, они объединяются в [1,6].
Пример 2.
Входные данные: intervals = [ [1,4], [4,5] ]
Результат: [ [1,5] ]
Пояснение: Интервалы [1,4] и [4,5] считаются перекрывающимися.
Решение.
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> mergedIntervals;
sort(intervals.begin(), intervals.end());
int start = intervals[0][0];
int end = intervals[0][1];
for (auto interval : intervals) {
if (interval[0] <= end) {
end = max(end, interval[1]);
} else {
mergedIntervals.push_back({start, end});
start = interval[0];
end = interval[1];
}
}
mergedIntervals.push_back({start, end});
return mergedIntervals;
}
};