2021-03-03:一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间 。你来安排宣讲的日程,要求会议室进行的宣讲的场次最多。 返回最多的宣讲场次。
福哥答案2021-03-03:
贪心算法。
1.按结束时间排序。
2.for循环中,当前时间点小于会议的开始时间点,需要计数。当前时间点变成会议的结束时间点。
代码用golang编写,代码如下:
package main import ( "fmt" "sort" ) func main() { programs := make([]*Program, 3) programs[0] = &Program{1, 27} programs[1] = &Program{26, 31} programs[2] = &Program{29, 300} ret := bestArrange(programs) fmt.Println(ret) } // 会议的开始时间和结束时间,都是数值,不会 < 0 func bestArrange(programs []*Program) int { //按会议的结束时间排序 sort.SliceIsSorted(programs, func(i, j int) bool { return programs[i].end < programs[j].end }) programsLen := len(programs) timeLine := 0 result := 0 // 依次遍历每一个会议,结束时间早的会议先遍历 for i := 0; i < programsLen; i++ { if timeLine <= programs[i].start { result++ timeLine = programs[i].end } } return result } type Program struct { start int end int }
执行结果如下: