安排讲座25-02-09★

安排讲座 #

题目描述 #

小明是一位的科学家，不久前他参加了一场重要的国际科学大会，展示了他的最新研究成果。现在，他计划在一所高校举办讲座，以分享他的研究成果。

然而，不同的大学班级有不同的课程安排，因此小明需要根据当天的大学生日程表来决定最佳的讲座时间。在这份日程表上，记录着各个班级的课余时间段，这些时间段都是整数。请问小明应该如何安排他的讲座，以便让尽可能多的班级参加？ 注意，同一个时刻只能有一个班级参加讲座

输入描述 #

第一行为一个整数 N，代表有 N 个班级 后续有 N 行，每行两个整数，代表了不同班级的课余时间段

输出描述 #

输出一个正整数，代表最多能安排多少场讲座。

输入示例 #
5
4 5
6 7
6 8
7 10
9 11
输出示例 #
3
提示信息 #

因为不同班级的课余时间不同，而小明每个时间段只能安排一场讲座。

每场讲座只有一个班级能够参加。

小明只能选择课余时间段为 [[4, 5], [6, 7], [7, 10]] 或 [[4, 5], [6, 7], [9, 11]] 等没有时间冲突的班级（课余时间段连续的情况不算冲突），所以在输入用例中，小明最多只能安排三场讲座。

数据范围： 1 <= N < 100。 1 <= 课余时间数字范围 <= 24。

解答 #

1 贪心 #

按照结束时间从低到高进行排序，从直觉上讲，越早结束，越方便进行安排下一场的讲座

import java.io.*;
import java.util.*;
   
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line=in.readLine();
        int num=Integer.parseInt(line);
        int tmp=num;
        int[][] arr=new int[num][2];
        int i=0;
        while(tmp>0){
            line=in.readLine();
            String[] tempArr=line.split(" ");
            arr[i][0]=Integer.parseInt(tempArr[0]);
            arr[i][1]=Integer.parseInt(tempArr[1]);
            tmp--;
            i++;
        }
        Arrays.sort(arr,(r1,r2)->Integer.compare(r1[1],r2[1]));
        int count=1;
        int end=arr[0][1];
        for(int j=1;j<num;j++){
            if(end<=arr[j][0]){
                count++;
                end=arr[j][1];
            }
        }
        out.println(count);
        out.flush();
    }
}

但是存在超时的情况，手写排序的算法可以解决这个问题

import java.io.*;
import java.util.*;
   
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line=in.readLine();
        int num=Integer.parseInt(line);
        int tmp=num;
        int[][] arr=new int[num][2];
        int ii=0;
        while(tmp>0){
            line=in.readLine();
            String[] tempArr=line.split(" ");
            arr[ii][0]=Integer.parseInt(tempArr[0]);
            arr[ii][1]=Integer.parseInt(tempArr[1]);
            tmp--;
            ii++;
        }
        // Arrays.sort(arr,(r1,r2)->Integer.compare(r1[1],r2[1]));
        for(int i = 0;i < num;i++){
            int index = i;
            for(int j = num - 1;j > i;j--){
                if(arr[j][1] < arr[index][1]){
                    index = j;
                }
            }
            int[] temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
        int count=1;
        int end=arr[0][1];
        for(int j=1;j<num;j++){
            if(end<=arr[j][0]){
                count++;
                end=arr[j][1];
            }
        }
        out.println(count);
        out.flush();
    }
}
  • 时间复杂度：
    • 排序需要 O*(NlogN)。
    • 遍历选择过程只需要 O*(N)。
    • 因此总时间复杂度为 O(Nlog⁡N)。
  • 空间复杂度：
    • 存储区间数组需要 O(N)的空间。
    • 因此空间复杂度为 O(N)。

2 动态规划 #

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
 
        int[][] intervals = new int[N][2];
        for (int i = 0; i < N; i++) {
            intervals[i][0] = sc.nextInt();
            intervals[i][1] = sc.nextInt();
        }
 
        // 1. 先对区间按照结束时间进行排序
        Arrays.sort(intervals, (a, b) -> {
            if (a[1] == b[1]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });
 
        // 2. 定义 dp[i]：截止到第 i 个区间(含)，最多能选到多少个不冲突区间
        int[] dp = new int[N];
        dp[0] = 1; // 第一个区间一定能选
 
        for (int i = 1; i < N; i++) {
            // (1) 不选当前区间i
            int notChoose = dp[i - 1];
            // (2) 选当前区间i
            //     - 找到与 i 不冲突的区间 j（j < i）
            int choose = 1; // 选了自己
            // 从 i-1 往前找, 找到第一个 intervals[j].end <= intervals[i].start
            // 注意端点相等不冲突, 所以 <= 就可以
            for (int j = i - 1; j >= 0; j--) {
                if (intervals[j][1] <= intervals[i][0]) {
                    choose = dp[j] + 1;
                    break;
                }
            }
 
            dp[i] = Math.max(notChoose, choose);
        }
 
        // dp[N-1] 即为最多可安排的讲座数
        System.out.println(dp[N - 1]);
    }
}
  1. 排序：同样先对区间按照开始时间或结束时间进行排序（方便后续状态转移）。
  2. 定义状态：
    • 设 dp[i] 表示在所有只考虑 前 i 个区间（按某种排序方式时）的情况下，能够得到的最大不冲突区间数。
  3. 状态转移：
    • 对于dp[i]，我们有两种选择：
      1. 不选第 i 个区间，则 dp[i] = dp[i-1]。
      2. 选第 i 个区间，那么需要在第 i 个区间之前选一个不会与 i 冲突的区间 j（j < i），并且 j 要尽量靠近 i，即 intervals[j].end <= intervals[i].start。则 dp[i] = dp[j] + 1因此 dp[i] = max(dp[i-1], 1 + dp[j])（j 使得区间 j 与 i 不冲突）。
  4. 取最大值：
    • 最后的结果就是 dp[N]（或 dp[n-1] 如果 dp 数组以 0~n-1 为索引）。

时间复杂度：

  • 排序：O*(Nlog*N)。
  • DP：对于每个 i，最坏情况要往前找 j，最多找 ii 次，即 O(N)。所以 DP 部分约O*(*N^2)。
  • 总体：O(N^2)。

空间复杂度：

  • 需要一个 dp 数组，大小为 O*(*N)。
  • 加上存储区间所需的O*(*N)。
  • 总体：O(N)。
顶部 首页 上一篇 下一篇