题解 | 主持人调度（二）

import java.util.*;


public class Solution {
    /**
     * 贪心算法
     * <p>
     * 不要将开始时间和结束时间作为一个整体看，先将开始时间和结束时间分开
     * 将开始时间和结束时间分开并排序
     * 先固定一个结束时间，遍历开始时间，如果开始时间小于结束时间，主持人就加 1
     * 如果开始时间大于结束时间，就可以重复使用一个主持人，主持人数不变，将结束时间后移一个，接着遍历开始时间
     */
    public int minmumNumberOfHost(int n, int[][] startEnd) {
        if (n == 0 || startEnd == null) {
            return 0;
        }
        int[] start = new int[n];
        int[] end = new int[n];
        for (int i = 0; i < n; i++) {
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int host = 0;
        int endIndex = 0;
        for (int startIndex = 0; startIndex < n; startIndex++) {
            if (start[startIndex] < end[endIndex]) {
                host++;
            } else {
                endIndex++;
            }
        }
        return host;
    }
}