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;
};

参考资料