问题
一些项目要占用一个会议室宣讲, 会议室不能同时容纳两个项目的宣讲. 给定每个项目的开始和结束时间 (输入为数组, 其中是一个个具体的项目), 合理安排宣讲日程, 使得会议室进行的宣讲场次最多, 返回这个最多的场次
题解
本题不可按开始时间排序, 若某个宣讲开始时间早但持续时间长, 可能不如多个晚开始的宣讲场次多; 也不可按持续时间长短, 某个短时间的宣讲可能与其它宣讲的起始时间重叠.
Java
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
| class Program {
int start;
int end;
public Program(int start, int end) {
this.start = start;
this.end = end;
}
}
public class BestArrange {
public static int bestArrange(Program[] programs, int start) {
Arrays.sort(programs, (a, b) -> a.end - b.end);
int result = 0;
for (Program program : programs) {
if (start <= program.start) {
result++;
start = program.end;
}
}
return result;
}
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Program:
def __init__(self, start, end):
self.start = start
self.end = end
def get_best_arrange(programs, start):
programs.sort(key=lambda x: x.end)
result = 0
for program in programs:
if start <= program.start:
result += 1
start = program.end
return result
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| type Program struct {
start, end int
}
func getBestArrange(programs []Program, start int) int {
for i := 0; i < len(programs); i++ {
for j := 0; j < len(programs)-1; j++ {
if programs[j].end > programs[j+1].end {
programs[j], programs[j+1] = programs[j+1], programs[j]
}
}
}
result := 0
for _, program := range programs {
if start <= program.start {
result++
start = program.end
}
}
return result
}
|