推 SecondRun: 球內推 02/18 15:58
→ sc95819200: 球內推 02/18 16:01
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/meeting-rooms-iii/description
: 2402. Meeting Rooms III
: 給你一個數字 n 和一個陣列meetings[]，meetings[i] = [starti, endi]，n表示你有
: 幾個房間，meetings[]表示多個會議的開始時間和結束時間，會議按照以下規則進行安排
: 1.會議會被安排在沒人使用且編號最小的房間
: 2.如果沒有房間可用，會議會被延遲，消耗的時間和原本的時間相同。
: 3.當延遲的會議有房間可用時，較早開始的會議有較高的優先權。
: 找出哪個房間被用最多次，如果有多個房間使用次數相同返回編號最小的。
思路：
建立一個heap，裡面放目前使用的會議室[2]int{結束時間,使用的會議室ID}
rec紀錄每個會議室使用次數，chk紀錄這個會議室有沒有在用
每次都去檢查目前在使用的會議室的結束時間是不是比這個會議的開始時間還早
是的話就pop出來
接著檢查現在有沒有空的會議室
1.沒有
從heap pop出一個房間，接著push目前這個會議資訊進到heap
2.有
去找目前沒在用的房間ID最小的
並將這個會議資訊push到heap裡面
最後去找rec裡面值最大的會議室
golang code :
type h [][2]int
func (this h) Len() int { return len(this) }
func (this h) Less(i, j int) bool {
if this[i][0] != this[j][0] {
return this[i][0] < this[j][0]
} else {
return this[i][1] < this[j][1]
}
}
func (this h) Swap(i, j int) { this[i], this[j] = this[j], this[i] }
func (this *h) Pop() interface{} {
n := len(*this)
x := (*this)[n-1]
*this = (*this)[:n-1]
return x
}
func (this *h) Push(x interface{}) {
(*this) = append(*this, x.([2]int))
}
func mostBooked(n int, meetings [][]int) int {
slices.SortFunc[[][]int](meetings, func(a, b []int) int {
return a[0] - b[0]
})
rec := make([]int, n)
h := h{}
idx := 0
chk := make([]bool, n)
for i := 0; i < len(meetings); i++ {
for len(h) > 0 && h[0][0] <= meetings[i][0] {
temp := heap.Pop(&h).([2]int)
chk[temp[1]] = false
}
if len(h) == n { //房間是滿的
now := heap.Pop(&h).([2]int)
time := now[0] + meetings[i][1] - meetings[i][0]
rec[now[1]]++
heap.Push(&h, [2]int{time, now[1]})
continue
}
for i := 0; i < n; i++ {
if !chk[i] {
idx = i
break
}
}
rec[idx]++
chk[idx] = true
heap.Push(&h, [2]int{meetings[i][1], idx})
}
ans := -1
max := 0
for i := 0; i < n; i++ {
if rec[i] > max {
max = rec[i]
ans = i
}
}
return ans
}
這個方法滿爛的
不過我也懶得想了，我就爛
明天假期結束好憂鬱
我沒想上班，好想轉職
我投的那些職缺能不能給個機會
拜託啦
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.92.238 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708242315.A.CC5.html