给一个动态规划问题与校园开设活动相关的题材并给出相应的Java题解,给出输入输出描述和几个样例
时间: 2024-05-29 16:11:37 浏览: 17
题目描述:
假设你是一位校园组织的活动策划师,你需要为你的学校策划一系列活动。每个活动都有一个开始时间和结束时间,如果两个活动时间有重叠,就不能同时举行。你需要选择一些活动,使得它们之间没有时间上的冲突,并且能够举办最多的活动。
输入描述:
第一行输入一个整数n,代表活动的总数。接下来的n行,每行输入两个整数,分别代表该活动的开始时间和结束时间。
输出描述:
输出一个整数,代表能够举办的最多活动数量。
样例输入:
5
1 3
2 4
3 5
4 6
5 7
样例输出:
3
Java题解:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 定义一个数组存储每个活动的开始时间和结束时间
int[][] activities = new int[n][2];
for (int i = 0; i < n; i++) {
activities[i][0] = sc.nextInt();
activities[i][1] = sc.nextInt();
}
// 按照结束时间从小到大排序
Arrays.sort(activities, Comparator.comparingInt(o -> o[1]));
// 定义一个数组存储以第i个活动为结尾的最多活动数量
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
// 找到第一个结束时间早于当前活动开始时间的活动
int j = i - 1;
while (j >= 0 && activities[j][1] > activities[i][0]) {
j--;
}
// 如果找到了这样的活动,dp[i] = dp[j] + 1
if (j >= 0) {
dp[i] = dp[j] + 1;
}
// 否则,dp[i] = 1
else {
dp[i] = 1;
}
// 更新最大值
dp[i] = Math.max(dp[i], dp[i - 1]);
}
// 输出最大值
System.out.println(dp[n - 1]);
}
}
时间复杂度:O(n^2)
空间复杂度:O(n)