区间调度.md

区间调度

给你很多形如 [start, end] 的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。

int intervalSchedule(int[][] intvs) {}

举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交， 即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。

这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间， 请问你今天最多能参加几个活动呢？ 显然你一个人不能同时参加两个活动，所以说这个问题就是求这些时间区间的最大不相交子集。

const intervalSchedule = function (intvs) {
    if (intvs.length === 0) {
        return 0;
    }
    
    const sortArray = intvs.sort((a, b) => a[1] - b[1]); // 根据 end 升序排列
    let xEnd = sortArray[0][1];
    let count = 1; // 互不相交的区间
    
    for (item of intvs) {
        const start = item[0];
        
        if (start >= xEnd) {
            count++;
            xEnd = item[1];
        }
    }
    
    return count;
}