โปรแกรมหาเงินเดือนขั้นต่ำสำหรับนักเขียนโค้ดที่ทำงานดีใน Python

สมมติว่าเรามีรายการ ratings แสดงคะแนนประสิทธิภาพ ผู้จัดการจ่าย 1000 บาทต่อคน แต่ถ้าสองคนติดกัน คนที่ทำงานดีกว่าต้องได้มากกว่าอีกคนอย่างน้อย 1000 บาท หาเงินรวมขั้นต่ำ

ตัวอย่าง: ratings = [1, 2, 5, 1] ผลลัพธ์ 7000 (จ่ายเป็น [1000, 2000, 3000, 1000])

ขั้นตอนการแก้ปัญหา (Two-pass Greedy - Candy Problem)

1. pay = [1] * len(ratings)
2. Left-to-right: หาก ratings[i-1] ให้ pay[i] = pay[i-1] + 1
3. Right-to-left: หาก ratings[i+1] ให้ pay[i] = max(pay[i], pay[i+1] + 1)
4. คืนค่า sum(pay) * 1000

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

class Solution:
    def solve(self, ratings):
        pay = [1] * len(ratings)
        
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                pay[i] = pay[i-1] + 1
        
        for i in range(len(ratings)-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                pay[i] = max(pay[i], pay[i+1] + 1)
        
        return sum(pay) * 1000

ob = Solution()
ratings = [1, 2, 5, 1]
print(ob.solve(ratings))  # Output: 7000

อินพุต

[1, 2, 5, 1]

เอาต์พุต

7000