贪心算法训练 活动安排

Ⅰ 题目 安排场次

有n个需要在同一天使用同一个教室的活动a1,a2,…,an,教室同一时刻只能由一个活动使用。
每个活动ai都有一个开始时间si和结束时间fi 。
一旦被选择后,活动ai就占据半开时间区间[si,fi)。
如果[si,fi]和[sj,fj]互不重叠,ai和aj两个活动就可以被安排在这一天。
该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。

Ⅱ 大体思路:

主要练习贪心算法。贪心算法的核心是 无后效性,即 当前的选择既不改变之前的状态,也不会影响以后的状态。
在安排场次中,可以贪心将每次的结束时间最早的先安排。
整体的思路如下: 
    ① 输入一个整数,表示输入的活动的个数;
    ② 放在数组里面并初始化;
    ③ 按照结束时间进行排序;
     ④ 判断下一个的开始时间是不是大于上一个的结束时间;
     ⑤ 计数

Ⅲ部分代码

1
2
3
4
5
6
7
8
9
10
private static int greed_activity(int[][] arrAct) {
int count = 1,point = 1;
for(int i = 2; i < arrAct.length; i++){
if(arrAct[i][0] > arrAct[point][1] ){//下一个活动的开始时间大于当前活动的结束时间
point = i;
count ++;
}
}
return count;
}

Ⅳ 全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;
public class SortByTime {
private static Scanner sc;
public static void main(String[] args) {
sc = new Scanner(System.in);
int N = sc.nextInt();//保存个数
int arrAct[][] = new int[N+1][2];//用数组来模拟场次活动的开始时间和结束时间
for(int i = 1; i < N+1; i++){ // 初始化每次活动的开始时间和结束时间
arrAct[i][0] = sc.nextInt();
arrAct[i][1] = sc.nextInt();
}
sort(arrAct);//按照结束时间进行排序
int number = greed_activity(arrAct);
System.out.println("最多的场次是 " + number + "次");
}
/**
* 贪婪 核心代码
* */
private static int greed_activity(int[][] arrAct) {
int count = 1,point = 1;
for(int i = 2; i < arrAct.length; i++){
if(arrAct[i][0] > arrAct[point][1] ){//下一个活动的开始时间大于当前活动的结束时间
point = i;
count ++;
}
}
return count;
}
/**
* 排序: 使用的插入排序
* **/
private static void sort(int[][] arrAct) {
for(int i = 2; i < arrAct.length; i++){
int t = i;
while( t > 0 && (arrAct[t-1][1] > arrAct[t][1])){
int [] p = arrAct[t];
arrAct[t]= arrAct[t-1];
arrAct[t-1] = p;
t--;
}
}
}
}