1272. Remove Interval

leetcode medium

#csharp#hash-table#intervals#leetcode#math#medium#sort

Task

Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.

Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]

Output: [[0,1],[6,7]]

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public IList<IList<double>> RemoveInterval(IList<IList<double>> intervals, IList<double> toBeRemoved) {
        var result = new List<IList<double>>();
        foreach (var interval in intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.Add(new List<double> { interval[0], Math.Min(interval[1], toBeRemoved[0]) });
            }
            if (interval[1] > toBeRemoved[1]) {
                result.Add(new List<double> { Math.Max(interval[0], toBeRemoved[1]), interval[1] });
            }
        }
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<IList<double>> RemoveInterval(IList<IList<double>> intervals, IList<double> toBeRemoved) {
        var result = new List<IList<double>>();
        foreach (var interval in intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.push_back(new List<double> { interval[0], min(interval[1], toBeRemoved[0]) });
            }
            if (interval[1] > toBeRemoved[1]) {
                result.push_back(new List<double> { max(interval[0], toBeRemoved[1]), interval[1] });
            }
        }
        return result;
    }
}

Java solution

matched/original

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<int[]> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<int[]> result = new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.add(new int[]{interval[0], Math.min(interval[1], toBeRemoved[0])});
            }
            if (interval[1] > toBeRemoved[1]) {
                result.add(new int[]{Math.max(interval[0], toBeRemoved[1]), interval[1]});
            }
        }
        return result;
    }
}

Python solution

matched/original

def removeInterval(intervals, toBeRemoved):
    result = []
    for start, end in intervals:
        if start < toBeRemoved[0]:
            result.append([start, min(end, toBeRemoved[0])])
        if end > toBeRemoved[1]:
            result.append([max(start, toBeRemoved[1]), end])
    return result

Go solution

matched/original

func removeInterval(intervals [][]float64, toBeRemoved []float64) [][]float64 {
    result := [][]float64{}
    for _, interval := range intervals {
        if interval[0] < toBeRemoved[0] {
            result = append(result, []float64{interval[0], math.Min(interval[1], toBeRemoved[0])})
        }
        if interval[1] > toBeRemoved[1] {
            result = append(result, []float64{math.Max(interval[0], toBeRemoved[1]), interval[1]})
        }
    }
    return result
}

Explanation

Algorithm

Интерируйтесь по каждому интервалу в списке intervals.

Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов.

Добавляйте непересекающиеся части текущего интервала в результат.

😎