โปรแกรมรวม intervals และเรียงลำดับใน Python

สมมติว่ามีรายการ intervals ต้องการหา union ของพวกเขาเรียงตามลำดับ

ตัวอย่าง: inv = [[2,5],[4,10],[20,25]] ผลลัพธ์ [[2,10],[20,25]]

ขั้นตอนการแก้ปัญหา

1. เรียง intervals
2. ans = []
3. วน s, e ใน intervals:
   • ถ้า ans และ s <= ans[-1][1]: ans[-1][1] = max(ans[-1][1], e)
   • มิฉะนั้น: เพิ่ม [s,e] เข้า ans
4. คืน ans

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

class Solution:
    def solve(self, intervals):
        intervals.sort()
        ans = []
        for s, e in intervals:
            if ans and s <= ans[-1][1]:
                ans[-1][1] = max(ans[-1][1], e)
            else:
                ans.append([s, e])
        return ans

ob = Solution()
inv = [[2, 5], [4, 10], [20, 25]]
print(ob.solve(inv))

อินพุต

[[2, 5], [4, 10], [20, 25]]

เอาต์พุต

[[2, 10], [20, 25]]