+关注继续查看

3. 课程表 Course Schedule III

1 <= courses.length <= 10^4

1 <= durationi, lastDayi <= 10^4

package main

import (
"fmt"
"sort"
)

func scheduleCourse(courses [][]int) int {
// 按照截止日期升序排序
sort.Slice(courses, func(i, j int) bool {
return courses[i][1] < courses[j][1]
})

time := 0
selected := make([][]int, 0)
for _, c := range courses {
if time+c[0] <= c[1] {
selected = append(selected, []int{c[0], c[1]})
time += c[0]
sort.Slice(selected, func(i, j int) bool {
return selected[i][0] > selected[j][0]
})
} else if len(selected) > 0 && c[0] < selected[0][0] {
time += c[0] - selected[0][0]
selected[0] = []int{c[0], c[1]}
sort.Slice(selected, func(i, j int) bool {
return selected[i][0] > selected[j][0]
})
}
}

return len(selected)
}

func main() {
courses := [][]int{{100, 200}, {200, 1300}, {1000, 1250}, {2000, 3200}}
fmt.Println(scheduleCourse(courses))
courses = [][]int{{1, 2}}
fmt.Println(scheduleCourse(courses))
}

3

1

4. 课程表 Course Schedule IV

有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。

2 <= numCourses <= 100

0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)

prerequisites[i].length == 2

0 <= ai, bi <= n - 1

ai != bi

每一对 [ai, bi] 都 不同

先修课程图中没有环。

0 <= ui, vi <= n - 1

ui != vi

package main

import "fmt"

func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
// 构建课程图
n := numCourses
graph := make([][]int, n)
inDegree := make([]int, n)
for _, p := range prerequisites {
ai, bi := p[0], p[1]
graph[ai] = append(graph[ai], bi)
inDegree[bi]++
}

// BFS 拓扑排序
queue := make([]int, 0)
for i := 0; i < n; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
successors := make([][]int, n)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, neighbor := range graph[node] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
// 记录 successor 节点
successors[node] = append(successors[node], neighbor)
for _, s := range successors[neighbor] {
successors[node] = append(successors[node], s)
}
}
}

// 对每个查询进行检查
result := make([]bool, len(queries))
for i, q := range queries {
ui, vi := q[0], q[1]
for _, s := range successors[ui] {
if s == vi {
result[i] = true
break
}
}
}
return result
}

func main() {
numCourses := 2
prerequisites := [][]int{{1, 0}}
queries := [][]int{{0, 1}, {1, 0}}
fmt.Println(checkIfPrerequisite(numCourses, prerequisites, queries))
prerequisites = [][]int{}
queries = [][]int{{1, 0}, {0, 1}}
fmt.Println(checkIfPrerequisite(numCourses, prerequisites, queries))
}

[false true]

[false false]

|
4月前
|
Python
Python每日一练(20230518) 螺旋矩阵 I\II\III\IV Spiral Matrix
Python每日一练(20230518) 螺旋矩阵 I\II\III\IV Spiral Matrix
58 0
|
4月前
|
Python
Python每日一练(20230517) 最大连续1的个数 I\II\III
Python每日一练(20230517) 最大连续1的个数 I\II\III
67 0
|
4月前
|
Python
Python每日一练(20230516) 打家劫舍 I\II\III\IV HouseRobber
Python每日一练(20230516) 打家劫舍 I\II\III\IV HouseRobber
85 0
|
4月前
|

Python每日一练(20230515) 只出现一次的数字 I\II\III
Python每日一练(20230515) 只出现一次的数字 I\II\III
66 0
|
4月前
|

Python每日一练(20230514) 不同路径 I\II\III UniquePaths
Python每日一练(20230514) 不同路径 I\II\III UniquePaths
61 0
|
4月前
|
Python
Python每日一练(20230513) 粉刷房子 I\II\III Paint House
Python每日一练(20230513) 粉刷房子 I\II\III Paint House
66 0
|
4月前
|
Python
Python每日一练(20230512) 跳跃游戏 V\VI\VII
Python每日一练(20230512) 跳跃游戏 V\VI\VII
45 0
|
4月前
|

Python每日一练(20230511) 跳跃游戏 I\II\III\IV
Python每日一练(20230511) 跳跃游戏 I\II\III\IV
55 0
|
4月前
|
Python
Python每日一练(20230510) 石子游戏 VII\VIII\IX
Python每日一练(20230510) 石子游戏 VII\VIII\IX
40 0
|
4月前
|

Python每日一练(20230509) 石子游戏 IV\V\VI
Python每日一练(20230509) 石子游戏 IV\V\VI
61 0