56. Merge Intervals.txt

//Самое быстрое решение на leetcode. Всего один цикл.
//Сначала сортируем исходный вектор. Затем создаём переменные для записи начального и конечного значений интервала. Запускаем цикл по всем элементам исходного
//	вектора (кроме первого).
//Если Первое значение текущего элемента исходного вектора больше сохранённого конечного значения интвервала, то это значит перекрывающий интервал закончен.
//	Мы сохраняем его в вектор финального ответа. Далее переназначаем значения начального и конечного значений интервала на значения из текущего элемента исходного вектора.
//Иначе если второе значение текущего элемента исходного вектора меньше сохранённого конечного значения интвервала, то это значит, что значение текущего элемента
//	входит в перекрывающий интервал. Приваеваем значению конца интервала второе значение текущего элемента исходного вектора, и продолжаем цикл.
//Если мы подошли к конечному элементу исходного вектора, то просто записываем в финальный ответ значения начала и конца текущего интервала.
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int size = intervals.size();//Размер вектора intervals
        if (size <= 1) return intervals;//Если размер равен 1, то возвращаем вектор обратно
        sort(intervals.begin(), intervals.end());//Сортируем исходный вектор
        int start = intervals[0][0];//Начальное значение  
        int end = intervals[0][1];//Конечное значение
        vector<vector<int>> res;//Вектор финального ответа
        for (int i = 1; i < size; i++) {//Цикл по всем элементам исходного вектора intervals (кроме первого)
            if (intervals[i][0] > end) {//Если первое значение i-ого элемента исходного вектора больше записанного конечного значения end
                res.push_back({ start, end });//Значит перекрывающий интервал закончен, сохраняем в вектор ответа новый интервал
                start = intervals[i][0];//Присваеваем новые значения для стартового и конечного значения.
                end = intervals[i][1];
            }
            else if (intervals[i][1] > end) {//Если второе значение i-ого элемента исходного вектора меньше записанного конечного значения end
                end = intervals[i][1];//Перезаписываем новое конечное значение end.
            }
            if (i == size - 1) //Если мы подошли к конечноу элементу исходного ветора intervals
                res.push_back({ start, end });//Записываем в ответ последний интервал
        }
        return res;//Возвращаем ответ
    }
};

//Мой код. Сортируем исходный вектор. Сравниваем все элементов массива друг с другом. Очень медленно, по памяти бьёт больше 50% пользователей.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        for (int i = 0; i < intervals.size(); i++) {
            for (int j = i + 1; j < intervals.size(); j++) {
                if (intervals[i][0] <= intervals[j][0] && intervals[j][0] <= intervals[i][1]) {
                    if (intervals[i][0] <= intervals[j][1] && intervals[j][1] <= intervals[i][1]) {
                        intervals.erase(intervals.begin() + j);
                    }
                    else {
                        intervals[i][1] = intervals[j][1];
                        intervals.erase(intervals.begin() + j);
                    }
                    j--;
                }
            }
        }
        return intervals;
    }
};