Задача. Удаляем интервал
Задача. Вам дан отсортированный список непересекающихся интервалов, представляющих набор вещественных чисел 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