题解 | 主持人调度（二）

思路一：

● 对数组进行排序，如果区间开始下标相同，按区间结束下标从小到大排序，否则按区间开始下标排序

● 使用最小堆来获取最近最快结束的区间结束下标

import java.util.*;
public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        //如果开始时间相同，按结束时间从小到大排序，否则按开始时间排序
        Arrays.sort(startEnd, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return Integer.compare(o1[1], o2[1]);
                } else {
                    return Integer.compare(o1[0], o2[0]);
                }
            }
        });
        // 使用最小堆来获取最近最快结束的活动结束时间
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            int start = startEnd[i][0];
            int end = startEnd[i][1];
            if (minHeap.isEmpty()) {
                minHeap.add(end);
            } else if (minHeap.peek() <= start) {
                //如果当前开始时间大于等于之前某个活动的结束时间，说明可以让之前那个主持人继续主持当前的活动
                minHeap.poll();
                minHeap.add(end);
            } else {
                // 如果不满足，需要新派一个主持人
                minHeap.add(end);
            }
        }
        return minHeap.size();
    }
}

思路二：

● 使用两个数组，分别记录开始下标和结束下标，并对两个数组从小到大进行排序

● 遍历n个区间，如果某个区间开始下标大于之前之前区间结束的下标，则划分为同一组，无需增加新的分组

● 如果出现之前的区间的结束下标大于当前区间开始下标，则需要增加新的一组

import java.util.*;
public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        if (n == 0) {
            return 0;
        }
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = startEnd[i][0];
            ends[i] = startEnd[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        // 如果某个活动开始的时间大于之前活动结束的时候，不增加主持人
        // 若是出现之前活动结束时间晚于当前活动开始时间的，则需要增加主持人。
        int res = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (starts[i] >= ends[j]) {
                j++;
            } else {
                res++;
            }
        }
        return res;
    }
}