หาช่วงเวลาทำงานที่ดีที่สุด (Longest Well-Performing Interval) ใน Python

โจทย์: กำหนดลิสต์ hours แทนชั่วโมงทำงานต่อวัน วันที่ถือว่า "เหนื่อย" (tiring) คือวันที่ทำงาน > 8 ชั่วโมง ช่วงเวลาทำงานที่ดี (well-performing interval) คือช่วงที่จำนวนวันเหนื่อย > จำนวนวันไม่เหนื่อย หาความยาวช่วงที่ยาวที่สุด

ตัวอย่าง

Input: [9, 9, 6, 0, 6, 6, 9]
Output: 3 (ช่วง [9, 9, 6] มีวันเหนื่อย 2 วัน vs ไม่เหนื่อย 1 วัน)

อัลกอริทึม (Prefix Sum + Hash Map)

1. แปลงชั่วโมงเป็นคะแนน: >8 = +1, ≤8 = -1
2. คำนวณ prefix sum สะสม
3. ใช้ hash map เก็บดัชนีแรกที่เจอแต่ละค่า prefix sum
4. หาช่วงที่ prefix sum เพิ่มขึ้น (บ่งบอกวันเหนื่อยมากกว่า)

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

class Solution(object):
    def longestWPI(self, hours):
        temp = 0      # prefix sum
        ans = 0       # คำตอบ
        d = {}        # hash map: prefix_sum -> first_index
        corner = 0    # flag: มีวันเหนื่อยอย่างน้อย 1 วัน
        
        for i in range(len(hours)):
            # อัปเดต prefix sum
            temp += 1 if hours[i] > 8 else -1
            
            if hours[i] > 8:
                corner = 1
            
            # ถ้า prefix sum > 0 หมายถึงช่วง [0..i] ดี
            if temp > 0:
                ans = max(ans, i + 1)
            
            # บันทึกดัชนีแรกของ prefix sum นี้
            if temp not in d:
                d[temp] = i
            
            # ถ้ามี prefix_sum - 1 อยู่แล้ว ช่วงระหว่างนั้นดี
            if temp - 1 in d:
                ans = max(ans, i - d[temp - 1])
        
        return max(ans, 0)

# ทดสอบ
ob = Solution()
print(ob.longestWPI([9, 9, 6, 0, 6, 6, 9]))  # Output: 3

ตัวอย่าง Input/Output

Input: [9,9,6,0,6,6,9]
Output: 3

ความซับซ้อน: Time O(n), Space O(n) - เหมาะสำหรับข้อมูลขนาดใหญ่