ให้ลิสต์ nums แสดงเวลาที่รถบัสต้องมาถึงแต่ละป้าย รถบัสวิ่งไปข้างหน้าเท่านั้น หาจำนวนรถบัสน้อยที่สุดที่ครอบคลุมทุกป้าย
ตัวอย่าง: [1,2,7,9,3,4] → 2 คัน (คัน 1: 1,2,3,4; คัน 2: 7,9)
อัลกอริธึม Greedy
- เดินจากซ้ายไปขวา ถ้ายังไม่ได้มอบหมายป้ายนี้ ให้สร้างรถบัสใหม่
- จากป้ายนี้ หาป้ายถัดไปที่เวลา > ปัจจุบัน และยังไม่ถูกมอบหมาย → มอบหมายให้รถบัสคันนี้
การนำไปใช้
class Solution:
def solve(self, nums):
ans = 0
seen = [False] * len(nums)
for i, n in enumerate(nums):
if not seen[i]:
seen[i] = True
ans += 1
prev = n
for j in range(i+1, len(nums)):
if nums[j] > prev and not seen[j]:
seen[j] = True
prev = nums[j]
return ans
ob = Solution()
print(ob.solve([1,2,7,9,3,4])) # 2
