365算法每日学计划
40打卡:
思路:
贪心思想解决。
其实,就是求尽可能多的不相交的区间。将时间区间按照结束时间升序排列,如果结束时间相同,按开始时间降序排列。
具体来说,对开始时间和结束时间进行排序,如果活动的开始时间能够大于上一次活动的结束时间,活动的数量就+1.
import java.util.Scanner;
public class _40 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int[] results = new int[num];
for (int i = 0; i < num; i++) {
int a = scanner.nextInt();
int[] startTimes = new int[a];
int[] endTimes = new int[a];
for (int j = 0; j < a; j++) {
startTimes[j] = scanner.nextInt();
endTimes[j] = scanner.nextInt();
}
results[i] = solve(startTimes, endTimes);
}
for (Integer result : results) {
System.out.println(result);
}
}
private static int solve(int[] startTime, int[] endTime) {
int maxresult = 1;
//冒泡排序,对startTime和endTime数据进行排序
for (int i = 0; i < endTime.length - 1; i++) {
boolean flag = true;
for (int j = 1; j < endTime.length - i; j++) {
if (endTime[j - 1] > endTime[j]) {
int temp = endTime[j - 1];
endTime[j - 1] = endTime[j];
endTime[j] = temp;
int temp2 = startTime[j - 1];
startTime[j - 1] = startTime[j];
startTime[j] = temp2;
flag = false;
}
}
if (flag) {
break;
}
}
// 记录上一次活动的结束时间
int key = endTime[0];
for (int i = 1; i < endTime.length; i++) {
// 如果活动的开始时间能够大于上一次活动的结束时间
if (startTime[i] - key >= 1) {
//计数+1
maxresult++;
//保存结束时间
key = endTime[i];
}
}
return maxresult;
}
}
觉得有用就转发分享一下吧