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