คราวนี้สมมติว่าเราเป็นผู้จัดการรถไฟ

ซึ่งมีแค่ 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

จบ