คำอธิบายปัญหา
กำหนดลิสต์ช่วง intervals แต่ละช่วง [start, end] หาจำนวนช่วงที่ **อยู่ภายในอีกช่วงหนึ่งอย่างสมบูรณ์** (นับครั้งเดียวแม้อยู่ในหลายช่วง) [s0,e0] ใน [s1,e1] ถ้า s0 ≥ s1 และ e0 ≤ e1
ตัวอย่าง
intervals = [[2,6],[3,4],[4,7],[5,5]] → Output: 2
- [3,4] ใน [2,6]
- [5,5] ใน [4,7]
ขั้นตอนการแก้ปัญหา (Sorting)
- เรียงช่วง:
startน้อยไปมาก,startเท่ากัน เรียงendมากไปน้อย - วนลูป เก็บ
end_mx= end สูงสุดที่เจอมา - ถ้า
end <= end_mx→ อยู่ในช่วงก่อนหน้า นับ +1 - อัปเดต
end_mx = max(end_mx, end)
การตนการทำงาน (Python)
def solve(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: (x[0], -x[1]))
end_mx = float("-inf")
ans = 0
for start, end in intervals:
if end <= end_mx:
ans += 1
end_mx = max(end_mx, end)
return ans
intervals = [[2, 6], [3, 4], [4, 7], [5, 5]]
print(solve(intervals)) # Output: 2
อินพุต / เอาต์พุต
Input: [[2, 6], [3, 4], [4, 7], [5, 5]] Output: 2
