435. Non-overlapping Intervals

LeetCode medium original: C# #array #csharp #intervals #leetcode #medium #sort

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

Дан Array интервалов intervals, где intervals[i] = [starti, endi]. return минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Beispiel:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

C# Lösung

zugeordnet/original

using System;
using System.Collections.Generic;
public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        int ans = 0;
        int k = int.MinValue;
        
        foreach (var interval in intervals) {
            int x = interval[0];
            int y = interval[1];
            if (x >= k) {
                k = y;
            } else {
                ans++;
            }
        }
        
        return ans;
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#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 int EraseOverlapIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        int ans = 0;
        int k = int.MinValue;
        
        foreach (var interval in intervals) {
            int x = interval[0];
            int y = interval[1];
            if (x >= k) {
                k = y;
            } else {
                ans++;
            }
        }
        
        return ans;
    }
}

Java Lösung

zugeordnet/original

import java.util.Arrays;

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int ans = 0;
        int k = Integer.MIN_VALUE;
        
        for (int[] interval : intervals) {
            int x = interval[0];
            int y = interval[1];
            if (x >= k) {
                k = y;
            } else {
                ans++;
            }
        }
        
        return ans;
    }
}

JavaScript Lösung

zugeordnet/original

var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    let ans = 0;
    let k = -Infinity;
    
    for (const [x, y] of intervals) {
        if (x >= k) {
            k = y;
        } else {
            ans++;
        }
    }
    
    return ans;
};

Python Lösung

zugeordnet/original

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        
        return ans
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        
        return ans

Go Lösung

zugeordnet/original

import (
    "sort"
    "math"
)

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    ans := 0
    k := math.MinInt32
    
    for _, interval := range intervals {
        x := interval[0]
        y := interval[1]
        if x >= k {
            k = y
        } else {
            ans++
        }
    }
    
    return ans
}

Algorithm

Отсортируйте интервалы по времени окончания.

Инициализируйте переменную ответа ans = 0 и Ganzzahl k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, наBeispiel, INT_MIN.

Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. return ans.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.