หาระยะทางสูงสุดระหว่างเมืองกับสถานีที่ใกล้ที่สุดใน Python

โจทย์: มี N เมือง (0 ถึง N-1) และรายการเมืองที่มีสถานี หาระยะทางสูงสุดจากเมืองใดเมืองหนึ่งไปสถานีที่ใกล้ที่สุด

ตัวอย่าง: N=6, stations=[2,4] → เมือง 0 ห่าง 2, เมือง 1 ห่าง 1, เมือง 3 ห่าง 1, เมือง 5 ห่าง 1 → max = 2

อัลกอริทึม O(N)

1. สร้าง boolean array station_present ขนาด N
2. เดินสแกนซ้ายไปขวา นับระยะห่างจากสถานีล่าสุด (dist)
3. เมื่อเจอสถานี → อัปเดต max_dist = max(max_dist, (dist+1)//2) รีเซ็ต dist=0
4. หลังลูป → max(max_dist, dist) (สำหรับช่วงท้ายที่ไม่มีสถานี)

ตัวอย่างโค้ด

def get_max_dist(N, station):
    station_present = [False] * N
    for city in station:
        station_present[city] = True
    
    dist = 0
    max_dist = min(station)  # ระยะจากเมือง 0 ถึงสถานีแรก
    
    for city in range(N):
        if station_present[city]:
            max_dist = max((dist + 1) // 2, max_dist)
            dist = 0
        else:
            dist += 1
    
    return max(max_dist, dist)

print(get_max_dist(6, [2, 4]))  # 2

ผลลัพธ์

2

สรุป: Single pass O(N) time O(N) space (boolean array) คิดระยะห่างระหว่างสถานีติดกัน ÷ 2 (ปัดขึ้น) และพิจารณาขอบเขต 2 ด้าน