题目描述补充

题目：无重叠区间

给定一个区间的集合，每个区间都表示为闭区间 [start, end]，其中 start 是区间的起始位置，end 是区间的结束位置，且满足 start <= end。请找出需要移除的区间的最小数量，使得剩余区间互不重叠。

注意：

• 你可以认为区间的起始位置和结束位置都是非负整数。
• 区间 [1, 2] 和区间 [2, 3] 有一个公共点，因此它们被视为重叠区间。

示例

输入: [[1,2],[2,3],[3,4],[1,3]]

输出: 1

解释: 移除 [1,3] 后，剩下的区间 [1,2]、[2,3] 和 [3,4] 互不重叠。

PHP 示例代码

function eraseOverlapIntervals($intervals) {
    if (empty($intervals)) {
        return 0;
    }
    
    // 按照区间的结束位置进行排序
    usort($intervals, function($a, $b) {
        return $a[1] - $b[1];
    });
    
    $count = 1; // 至少保留一个区间
    $end = $intervals[0][1]; // 初始化为第一个区间的结束位置
    
    for ($i = 1; $i < count($intervals); $i++) {
        if ($intervals[$i][0] >= $end) {
            // 如果当前区间的起始位置大于或等于前一个区间的结束位置，说明不重叠
            $end = $intervals[$i][1]; // 更新结束位置
            $count++;
        }
    }
    
    // 需要移除的区间数量 = 总区间数 - 不重叠的区间数
    return count($intervals) - $count;
}

// 测试用例
$intervals = [[1,2],[2,3],[3,4],[1,3]];
echo eraseOverlapIntervals($intervals); // 输出 1

Python 示例代码

def eraseOverlapIntervals(intervals):
    if not intervals:
        return 0
    
    # 按照区间的结束位置进行排序
    intervals.sort(key=lambda x: x[1])
    
    count = 1  # 至少保留一个区间
    end = intervals[0][1]  # 初始化为第一个区间的结束位置
    
    for interval in intervals[1:]:
        if interval[0] >= end:
            # 如果当前区间的起始位置大于或等于前一个区间的结束位置，说明不重叠
            end = interval[1]  # 更新结束位置
            count += 1
    
    # 需要移除的区间数量 = 总区间数 - 不重叠的区间数
    return len(intervals) - count

# 测试用例
intervals = [[1,2],[2,3],[3,4],[1,3]]
print(eraseOverlapIntervals(intervals))  # 输出 1

JavaScript 示例代码

function eraseOverlapIntervals(intervals) {
    if (intervals.length === 0) {
        return 0;
    }
    
    // 按照区间的结束位置进行排序
    intervals.sort((a, b) => a[1] - b[1]);
    
    let count = 1; // 至少保留一个区间
    let end = intervals[0][1]; // 初始化为第一个区间的结束位置
    
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            // 如果当前区间的起始位置大于或等于前一个区间的结束位置，说明不重叠
            end = intervals[i][1]; // 更新结束位置
            count++;
        }
    }
    
    // 需要移除的区间数量 = 总区间数 - 不重叠的区间数
    return intervals.length - count;
}

// 测试用例
const intervals = [[1,2],[2,3],[3,4],[1,3]];
console.log(eraseOverlapIntervals(intervals)); // 输出 1

码小课网站中有更多相关内容分享给大家学习，希望大家能够继续深入学习算法和数据结构的知识，提高自己的编程能力。