435. Non-overlapping Intervals

Leetcode 問題: 435. Non-overlapping Intervals
Categories:
Tags:

題目

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

傳入一個陣列，包含數條 起點 及 終點 的連線資訊，找出刪除最少的連線數數量 讓彼此的連線是 不會相交（overlapping）

[1, 2] 及 [2, 3] 中間的 2 是彼此的終點及起點，這樣不算相交 overlapping

Example

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.

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

答案

為了能夠讓刪除的線越少越好，所以盡量將 越前面的線 及 長度越短的線 保留，可以保留最多的連線

JavaScript

按照整數區間連線的 起點 排序

  1. 按照連線的 起點 排序所有連線，若起點相同，則將 長度越短 的線排在前面
  2. 比較兩條連線
    • 若「目前連線」起點，比「前一個連線」終點還大：兩條連線沒有相交，不需要刪除任何線
      • 表示 目前連線 之前的所有連線都是沒有相交的，所以僅需要檢查 目前連線 終點後方的連線是否有相交
    • 若「目前連線」起點，比「前一個連線」終點還小：兩條線相交，需要刪除一條線，保留較短的線
  3. 回傳需要刪除連線數量
/**
 * @param {number[][]} intervalsList
 * @return {number}
 */
var eraseOverlapIntervals = function(intervalsList) {
    // 要移除的清單數量
    let eraseIntervalsCount = 0;
    if (intervalsList.length == 0) {
        // 如果沒有任何資料，直接回傳 0
        return eraseIntervalsCount;
    }

    // 排序清單大小(起點越小排前面)
    intervalsList.sort((a, b) => {
        if (a[0] < b[0]) {
            // 當 a[0] 第一個數字比 b[0] 小，a 較小排前面
            return -1;
        } else if (a[0] > b[0]) {
            // 當 a[0] 第一個數字比 b[0] 大，a 較大排後面
            return 1;
        } else {
            // a[0] 數字 與 b[0] 一樣大，表示起點一樣，將長度較短的放在前面
            if (a[1] < b[1]) {
                // 當 a[1] 第一個數字比 b[1] 小，a 較短，a 排前面
                return -1;
            } else {
                // 當 a[1] 第一個數字比 b[1] 大，a 較長，a 排後面
                return 1;
            }
        }
    });


    // 前一個點的結尾
    let previousEndPoint = intervalsList[0][1];

    // 比較後面所有的連線
    for (let i = 1; i < intervalsList.length; i++) {
        // 目前連線
        let currentInterval = intervalsList[i];
        // 目前連線：起點
        let currentStartPoint = currentInterval[0];
        // 目前連線：終點
        let currentEndPoint = currentInterval[1];

        if (currentStartPoint >= previousEndPoint) {
            // 若「目前連線」起點，比「前一個連線」終點還大：兩條連線沒有相交，不需要刪除任何線
            // 將目前要檢查的終點設定為「目前連線」的終點
            previousEndPoint = currentEndPoint;
        } else {
            // 若「目前連線」起點，比「前一個連線」終點還小：兩條線相交，需要刪除一條線
            eraseIntervalsCount++;
            // 將目前要檢查的終點設定為，在「目前連線」的終點與「前一個連線」的終點，取最小的那一個
            // 看看哪一條線最短就先優先保留
            previousEndPoint = Math.min(currentEndPoint, previousEndPoint);
        }
    }


    return eraseIntervalsCount;
};

按照整數區間連線的 終點 排序

  1. 按照連線的 終點 排序所有連線，若終點相同，則將 長度越短 的線排在前面
  2. 比較兩條連線
    • 若「目前連線」起點，比「前一個連線」終點還小：兩條線相交，需要刪除一條線
    • 若「目前連線」起點，比「前一個連線」終點還大：兩條連線沒有相交，可以保留的線多一條
      • 表示 目前連線 之前的所有連線都是沒有相交的，所以僅需要檢查 目前連線 終點後方的連線是否有相交
  3. 回傳需要刪除連線數量
/**
 * @param {number[][]} intervalsList
 * @return {number}
 */
var eraseOverlapIntervals = function(intervalsList) {

    if (intervalsList.length == 0) {
        // 如果沒有任何資料，直接回傳 0
        return 0;
    }

    // 排序清單大小(終點越小排前面)
    intervalsList.sort((a, b) => {
        if (a[1] < b[1]) {
            // 當 a[1] 數字比 b[1] 小，a 較小排前面
            return -1;
        } else if (a[1] > b[1]) {
            // 當 a[1] 數字比 b[1] 大，a 較大排後面
            return 1;
        } else {
            // a[1] 數字 與 b[1] 一樣大，表示終點一樣，將長度較短的放在前面
            if (a[0] < b[0]) {
                // 當 a[0] 第一個數字比 b[0] 小，a 較長，a 排後面
                return 1;
            } else {
                // 當 a[1] 第一個數字比 b[1] 大，a 較短，a 排前面
                return -1;
            }
        }
    });


    // 要保留的數字連線數量：起點的線是最短的會保留
    let keepIntervalsCount = 1;

    // 前一個點的結尾
    let previousEndPoint = intervalsList[0][1];

    // 比較後面所有的連線
    for (let i = 1; i < intervalsList.length; i++) {
        // 目前連線
        let currentInterval = intervalsList[i];
        // 目前連線：起點
        let currentStartPoint = currentInterval[0];
        // 目前連線：終點
        let currentEndPoint = currentInterval[1];

        if (currentStartPoint < previousEndPoint) {
            // 「目前連線起點」小於「先前連線終點」，兩條線相交
            continue;
        } else {
            // 「目前連線起點」大於等於「先前連線終點」，兩條線沒有相交
            // 表示在「目前連線終點」前的所有連線都是沒有相交的，接下來繼續檢查目前連線終點後面的連線
            previousEndPoint = currentEndPoint;
            // 可以保留的連線數量+1
            keepIntervalsCount++;
        }
    }

    // 需要刪除的連線數量：所有連線數量 - 可保留的連線數料
    let eraseIntervalsCount = intervalsList.length - keepIntervalsCount;

    return eraseIntervalsCount;
};

參考資料