Максимизируйте неперекрывающиеся интервалы, удалив минимальные интервалы.
Leetcode #435 Решение проблем среднего уровня с использованием жадного подхода.
Учитывая набор интервалов, найдите минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не перекрывались.
Пример:
Input: [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Когда возникает проблема минимизации или максимизации среднего, сразу приходит на ум жадный подход.
Да, ты прав! Мы собираемся решить ее с помощью жадного подхода.
Приступаем к решению проблемы
Учитывая эту проблему, у нас есть три случая перекрытия интервалов, которые могут возникнуть.
Примечание. Здесь, если конечная точка предыдущего интервала и начальная точка следующего интервала совпадают, это означает, что они не перекрываются.
Случай 1. Два интервала не перекрываются.
Случай 2. Два интервала перекрываются, и начальная точка текущего интервала меньше начальной точки предыдущего интервала, а конечная точка предыдущего интервала больше конечной точки текущего интервала.
Случай 3: Два интервала перекрываются, а начало текущего интервала меньше конечной точки предыдущего интервала.
Это три случая, которые нам необходимо учитывать при решении этой проблемы. Давайте посмотрим на схему для лучшего понимания этой проблемы.
Мы сохраним две переменные с именами prev и count.
- prev переменная, имеющая трек того, какой интервал необходимо сравнить с текущим интервалом.
- переменная count, имеющая количество no. интервалы были удалены.
Посмотрим на решение в javascript
Шаг 1: нам нужно сначала отсортировать интервалы на основе начальной точки. Это очень важный шаг, иначе мы не можем применить жадный подход к этой проблеме.
Затем интервалы итерации один за другим, изначально у нас нет правильных предыдущих интервалов, поэтому мы пропустили проверку 0-го индекса и начали с индекса 1.
Итак, предыдущая переменная изначально имеет значение 0
И count = 0 //Потому что мы изначально не удаляли никаких интервалов.
Мы увеличиваем счетчик только в том случае, если происходит перекрытие, в противном случае счетчик остается прежним.
И назначение переменной prev, если происходит неперекрытие или интервал prev больше текущего интервала.
prev = i;
если предыдущая конечная точка интервала больше, текущая начальная точка интервала означает, что произошло перекрытие, поэтому мы снова проверяем, присутствует ли оно в случае 2 или случае 3. если происходит какой-либо из случаев перекрытия, нам нужно увеличить счетчик.
Спасибо, что прочитали эту статью! Удачного кодирования ‹/›
