[LeetCode] No.435 Non-overlapping Intervals

9475 ワード
leetcode テキストリンク
質問リンク
LeetCode
質問する
ギャップの開始時間と終了時間を含む配列を返します.重複しないように、削除すべきギャップの数をできるだけ多くします.
に答える

完全ナビゲーションで問題にアクセスした場合、O(n 2)×2n)O(n^2\times 2^n)O(n2×2 n)時間的に複雑度が高く,問題を解決できない.
したがって,GRADYアルゴリズムを用いて問題を解決しなければならない.指定されたアレイを昇順に並べた場合、終了時間は

下図のように並べ替えます.
この場合、最初のギャップを選択して選択したギャップに重ねる場合は、ギャップを削除し、重ならない場合は次のギャップを選択します.
この場合、削除された間隔は、重複を避けるために削除された最大間隔です.
コード#コード#
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int answer = 0;
        List<Interval> intervalsList = Arrays.stream(intervals)
            .map(arr -> new Interval(arr[0],arr[1]))
            .collect(Collectors.toList());
        Collections.sort(intervalsList);
        
        int endTime = intervalsList.get(0).getEndTime();
        for(int i = 1; i<intervalsList.size(); i++) {
            if(endTime > intervalsList.get(i).getStartTime()){
                answer++;
                continue;
            }
            endTime = intervalsList.get(i).getEndTime();
        }
        
        return  answer;
        
    }
    class Interval implements Comparable<Interval>{
        int startTime;
        int endTime;
        
        Interval(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }
        
        int getStartTime(){return startTime;}
        int getEndTime(){return endTime;}
        
        @Override
        public int compareTo(Interval cmp) {
            return Integer.compare(endTime, cmp.endTime);
        }
        
        @Override
        public String toString() {
            return startTime + " to " + endTime;
        }
    }
}
プログラマー|Lv.1練習問題Part.5_JS
(BUGシリーズ)org.hibernate.boot.archive.spi.ArchiveException: Could not build ClassFile