題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=2037
題目要求:
如何合理安排看盡量多的完整節(jié)目?
image.png
做題思路:
該題的目的是將列表的節(jié)目盡可能多地完整地看一遍,于是就可以用貪心算法------區(qū)間調(diào)度------來求解.
我們將電視節(jié)目分為12個區(qū)間,要求完整看完區(qū)間,就不能有區(qū)間的覆蓋.同時要讓區(qū)間與區(qū)間的距離盡量小.
我們在選下一個節(jié)目時首先保證他開始的時間要在上一個節(jié)目結(jié)束之后，然后從所有符合條件的節(jié)目當中選取結(jié)束時間最早的即可.
于是可以對節(jié)目結(jié)束時間進行小到大的排序.如圖:
image.png
然后先選取第一個區(qū)間,然后以 " 下一個節(jié)目的開始時間 >= 上一個節(jié)目的結(jié)束時間 " 為條件逐個往下選擇.
代碼:
/*電視節(jié)目對象*/
public class TVshow {
private int start;
private int end;
public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
public TVshow(int start, int end) {
this.start = start;
this.end = end;
}
}
/*對節(jié)目排序*/
import java.util.Comparator;
public class Cmpimplements Comparator {
@Override
public int compare(TVshow o1, TVshow o2) {
return (o1.getEnd()>o2.getEnd())?1:-1;//按結(jié)束時間排序
}
}
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input =new Scanner(System.in);
while(input.hasNextLine()) {
int number = input.nextInt();
if(number ==0)break;
TVshow [] tVshows =new TVshow[number];//存放電視節(jié)目對象
for (int i =0;i < number;i++) {
int start_time = input.nextInt();
int end_time = input.nextInt();
tVshows[i] =new TVshow(start_time,end_time);//存放時間區(qū)間
}
Arrays.sort(tVshows,new Cmp());//排序
int value_num =0;//記錄最多可以看多少節(jié)目
int pre_etime =0;//上一個節(jié)目的結(jié)束時間
for (int i =0;i < number;i++) {
int stime = tVshows[i].getStart();
int etime = tVshows[i].getEnd();
if(stime >= pre_etime) { //判斷條件
value_num++;
pre_etime = etime;
}
}
System.out.println(value_num);
}
}
}
/*
12
1 3
3 4
0 7
3 8
2 9
5 10
6 12
4 14
10 15
8 18
15 19
15 20
*/
