描述

  • 有n个活动即将举办，每个活动都有开始时间与活动的结束时间，第i个活动的开始时间是 starti,第i个活动的结束时间是 endi,举办某个活动就需要为该活动准备一个活动主持人。

  • 一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第i个活动，那么该主持人在 (starti,endi)这个时间段不能参与其他任何活动。求为了成功举办这n个活动，最少需要多少名主持人。
    数据范围:


方法一

思路

  • 活动调度，模拟主持人分配
  • 不知道读者了不了解活动调度问题，活动调度是黑皮书《算法导论》贪心算法章节的第一个栗子，给你一组活动的起始时间和结束时间，选出一个最大的互不冲突的活动集。
  • 而本题可以说是活动调度问题的衍生，所以我们可以将主持人调度转换成活动调度，将所给活动集合划分成若干个活动集合，每个活动集合都是当前的最大的互不冲突的活动集，那么活动集合的数量即为题目所要求的最少主持人数量。
  • 下面介绍一下活动调度算法：
  • 具体的推导过程我就不细说了，感兴趣的可以去看黑皮书，这里用到了贪心思想，对于任意非空子问题Sk，am是Sk中结束时间最早的活动，则am在Sk的某个最大互不冲突的活动集中，也就是说对于所给的活动集合，只需在时间上不发生冲突的前提下，尽量选择结束时间早的活动，这样所选出的活动集即为最大互不冲突活动集。
  • 而为了求最少主持人数，只需要在找出一个最大互不冲突活动集后，继续对剩下的活动集合进行活动调度，找出第二个最大兼容活动集，依次类推直至所有活动均被分配。
  • 代码如下：
    import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 计算成功举办活动需要多少名主持人
   * @param n int整型 有n个活动
   * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
   * @return int整型
   * 通过活动调度解决问题
   */
  public int minmumNumberOfHost (int n, int[][] startEnd) {
      if (n == 0){
          return 0;
      }
      // 对活动按照开始时间进行升序排序
      Arrays.sort(startEnd,Comparator.comparingInt(o -> o[0]));
      // 辅助判断活动是否已经分配主持人
      boolean[] solved = new boolean[startEnd.length];
      int res = 0;
      // 模拟主持人分配
      while(activityOrder(startEnd,solved)){
          ++res;
      }
      return res;
  }
  // 活动调度算法，
  private boolean activityOrder(int[][] startEnd,boolean[] solved){
      // 初始活动结束时间
      int end = Integer.MIN_VALUE;
      // 判断所有活动是否都已经分配
      boolean flag = false;
      int i = 0;
      // 活动调度
      while(i < startEnd.length){
          if (!solved[i] && startEnd[i][0] >= end){
              solved[i] = true;
              flag = true;
              end = startEnd[i][1];
          }
          ++i;
      }
      return flag;
  }
}
  • 时间复杂度：，最坏情况是所有的活动都冲突了，总共要分配n个主持人，而每次活动调度需要n;
  • 空间复杂度：，一维数组辅助运算。

方法二

思路

  • 贪心，最小堆，排序
  • 开始结束时间相冲突的活动一定是需要不同的主持人主持的，故我们可以模拟活动的进行，同时进行的活动的最大数量就是需要的最少的主持人人数。
  • 由于活动需要按照时间线运行，所以需要先对所给的活动集按照开始时间进行升序排序。
  • 依据活动的结束时间创建最小堆p，p便是活动发生的场所，从左往右遍历升序活动集。
  • 堆空，则活动直接入栈，开始活动；
  • 堆非空，比较当前活动的开始时间与堆顶的活动的结束时间，若大于等于，则当前活动开始时，堆顶活动已经结束，所以弹出堆顶元素，继续与当前活动进行比较，直至堆空，或者时当前活动的开始时间小于堆顶活动结束时间。
  • 遍历结束，所需的最少主持人数即为最小堆中同时进行的最大活动数。
  • 参考下图示例：
    开始时间升序活动集为：[[1,2][1,3][2,4],[2,5],[3,6],[4,5],[5,6]];
    图片说明
  • 代码如下： 
import java.util.*;


public class Solution {
    // 活动类
    class Activity{
        int start;
        int end;
        public Activity(int start,int end){
            this.start = start;
            this.end = end;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     * 通过活动调度解决问题
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        if (n == 0){
            return 0;
        }
        // 按活动开始时间升序排序
        Arrays.sort(startEnd,Comparator.comparingInt(o -> o[0]));
        int count = 0;
        // 当前正在进行的活动,活动结束时间的最小堆
        PriorityQueue<Activity> parallelActivities = new PriorityQueue<>((o1,o2) -> o1.end - o2.end);
        for (int i = 0;i < n;++i){
            Activity activity = new Activity(startEnd[i][0],startEnd[i][1]);
            // 队空，直接入队
            if (parallelActivities.isEmpty()){
                parallelActivities.offer(activity);
            }
            // 队非空
            else {
                while(!parallelActivities.isEmpty()){
                    Activity a = parallelActivities.peek();
                    // 待执行活动在队首元素结束之后开始，弹出队首元素
                    if (activity.start >= a.end){
                        parallelActivities.poll();
                    }else{
                        break;
                    }
                }
                parallelActivities.offer(activity);
            }
            // 取最大值
            count = Math.max(parallelActivities.size(),count);
        }
        return count;
    }
}
  • 时间复杂度：，排序的时间复杂度为，之后的主持人调度是；
  • 空间复杂度：，使用最小堆存储活动，最坏情况下是。