คราวนี้สมมติว่าเราเป็นผู้จัดการรถไฟ
ซึ่งมีแค่ 2 สถานี คือ A กับ B
A กับ B มีตารางออกจากสถานีแน่นอน มีระยะเวลาเดินทางแน่นอน และมีระยะเวลาพักรถแน่นอน
เราต้องหาว่า เราต้องหารถมาวางไว้ที่สถานี A กี่คัน และสถานี B กี่คัน
อ่านต่อ
ที่นี่ วิธีคิดก็เอาตารางเวลามาเรียงกันทั้งหมด เราหยิบเที่ยวที่ออกเช้าสุดออกมา
เมื่อเดินไปถึงอีกสถานีนึง เราก็มาดูว่าตารางเวลาถัดไปของอีกสถานีนึงคืออะไร แล้วก็ตัดไปเรื่อยๆ
เริ่มกันเลย
let solve t set =
t คือระยะเวลาพักรถ
set คือ Set ของตารางเวลาซึ่งเป็น tuple ซึ่งเรียงดังนี้ เวลาออก เวลาถึง สถานี id
สถานีผมใช้เป็น boolean ถ้าเป็น true คือ สถานี A ถ้า false คือ สถานี B
let rec runTrip startTime station set =
let findFn (dep,_,i,_) = dep >= startTime && i = station
match Seq.tryFind findFn set with
| None -> set
| Some(it) -> let _,arr,_,_ = it
runTrip (arr+t) (not station) (Set.remove it set)
ถัดมาคือ function เดินรถ เช่น เดินรถจาก A ไป B ถึง B กี่โมง สามารถออกจาก B ไป A ได้อีกหรือไม่
ถ้าได้ (Some(it)) ก็ตัดออกจาก set ไปเรื่อยๆ
แต่ถ้าไม่ได้ (None) ก็คืนค่า set ที่ถูกตัดออกไป
let rec startTrip a b set =
if set = Set.empty
then a, b
else let startTime,_,station,_ = set.MinimumElement
let newSet = runTrip startTime station set
if station
then startTrip (a+1) b newSet
else startTrip a (b+1) newSet
และถัดมาคือ function ดูว่าต้องมีรถที่ A และ B อย่างละเท่าไหร่
หลักการคือ เอารถเที่ยวแรกออกมา แล้วโยนเข้าไปใน runTrip ก็จะได้ set ใหม่ที่หักตารางของรถคันนี้ออกไป
วนไปเรื่อยๆ จนไม่มี item ใน set (Set.empty) จะได้คำตอบออกมา
สุดท้ายคืนค่า
let a, b = startTrip 0 0 set
sprintf "%A %A" a b
จบ