Задачи
November 11

Задача. Удаляем интервал

Задача. Вам дан отсортированный список непересекающихся интервалов, представляющих набор вещественных чисел x, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Также дан интервал remove.

Верните исходный список интервалов без remove. То есть верните набор вещественных чисел, каждый x в котором находится в исходном списке интервалов, но не в remove.

Пример

intervals = [[0,2], [3,4], [5,7]]
remove = [1,6]
Output: [[0,1], [6,7]]

Разбор

Для решения задачи достаточно рассмотреть всевозможные пересечения интервалов. При обходе исходно списка интервалов, мы будем рассматривать текущий интервал с интервалом, который нужно будет удалить. При сравнении мы будем принимать решение: какие части текущего интервала оставлять в результате, а какие нет.

  • Случай 1: текущий интервал полностью входит в toBeRemoved, значит пропускаем его, он будет полностью удален.
  • Случай 2: текущий интервал не входит в toBeRemoved, поэтому сохраняем его полностью.
  • Случай 3: toBeRemoved полностью входит в текущий интервал. Сохраняем остатки текущего интервала с его начала и с конца.
  • Случай 4: начало текущего интервала не входит в toBeRemoved, поэтому сохраняем его
  • Случай 5: конец текущего интервала не входит в toBeRemoved, поэтому сохраняем его.

Реализация

public static IList<IList<int>> RemoveInterval(int[][] intervals, int[] toBeRemoved) {
    var list = new List<IList<int>>();
    for (int i = 0; i < intervals.Length; i++)
    {
        var cur = intervals[i];

        // текущий интервал полностью входит в toBeRemoved
        // пропускаем его, он будет удален
        if (toBeRemoved[0] <= cur[0] && cur[1] <= toBeRemoved[1])
        {
            continue;
        }
        // текущий интервал не входит в toBeRemoved -> сохраняем его полностью
        else if (cur[0] >= toBeRemoved[1] || cur[1] <= toBeRemoved[0])
        {
            list.Add(cur);
        }
        // в текущий интервал полностью входит toBeRemoved
        // сохраняем остатки интервала с его начала и с конца
        else if (cur[0] < toBeRemoved[0] && toBeRemoved[1] < cur[1])
        {
            list.Add(new int[] { cur[0], toBeRemoved[0] });
            list.Add(new int[] { toBeRemoved[1], cur[1]});
        }
        // начало текущего интервала не входит в toBeRemoved -> сохраняем его
        else if (cur[0] < toBeRemoved[0])
        {
            list.Add(new int[] { cur[0], toBeRemoved[0] });
        }
        // конец текущего интервала не входит в toBeRemoved -> сохраняем его
        else if (cur[0] < toBeRemoved[1])
        {
            list.Add(new int[] { toBeRemoved[1], cur[1] });
        }
    }

    return list; 
}

https://gist.github.com/unilecs/e93dff7bbade37f045b1caf694a6fa1b

Play-test

https://dotnetfiddle.net/9nCAXU