โปรแกรมนับจำนวนช่วงที่อยู่ภายในช่วงอื่นๆ ใน Python . ทั้งหมด

สมมติว่าเรามีรายการช่วงเวลา ในช่วงรายการนี้[i] มีค่า [start, end] เราต้องหาจำนวนช่วงที่อยู่ภายในช่วงอื่น หากมีช่วงที่ประกอบด้วยช่วงอื่นๆ หลายช่วงที่ควรนับเพียงครั้งเดียว ช่วง [s0, e0] อยู่ภายในช่วงอื่น [s1, e1] เมื่อ s0 ≤ s1 และ e0 ≥ e1

ดังนั้น หากอินพุตเหมือนช่วงเวลา =[[2, 6],[3, 4],[4, 7],[5, 5]] ผลลัพธ์จะเป็น 2 เพราะ [3, 4] และ [ 5, 5] อยู่ภายใน [2, 6] และ [4, 7] ตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้ารายการช่วงเวลาว่างเปล่า ดังนั้น
  • คืน 0
• เรียงลำดับรายการช่วงเวลาตามเวลาเริ่มต้น เมื่อเวลาเริ่มต้นเท่ากัน เรียงลำดับตามเวลาสิ้นสุดที่ลดลง
• end_mx :=-อินฟินิตี้
• ตอบ :=0
• สำหรับแต่ละคู่ (เริ่มต้น, สิ้นสุด) ในช่วงเวลา ให้ทำ
  • ถ้าจบ <=end_mx แล้ว
    • อัน :=ans + 1
  • end_mx :=สูงสุดของ end_mx และ end
• คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

[[2, 6],[3, 4],[4, 7],[5, 5]]

ผลลัพธ์

2