แยกรายการช่วงใน C ++

สมมติว่าเรามีช่วงปิดสองรายการ รายการช่วงแต่ละช่วงไม่ปะติดปะต่อแบบคู่และเรียงตามลำดับ เรามีจุดตัดกันของรายการช่วงเวลาทั้งสองนี้

เรารู้ว่าช่วงปิด [a, b] แสดงเป็น a <=b เซตของจำนวนจริง x ที่มี a <=x <=b. จุดตัดของช่วงปิดสองช่วงคือชุดของจำนวนจริงที่ว่างหรืออาจแสดงเป็นช่วงปิดก็ได้

ดังนั้นหากอินพุตเป็น A =[[0,2],[5,10],[13,23],[24,25]] และ B =[[1,5],[8,12],[ 15,24],[25,27]] แล้วผลลัพธ์จะเป็น [1,2],[5,5],[8,10],[15,23],[24,24],[25 ,25]].

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

• สร้างรายการ res ตั้งค่า I :=0 และ j :=0

• กำหนดวิธีการที่เรียกว่า intersect() ซึ่งจะใช้ a และ b -

• ถ้า a[0] <=b[0] และ a[1]>=b[0] แล้วคืนค่าเป็นจริง

• มิฉะนั้น เมื่อ b[0] <=a[0] และ b[1]>=a[0] คืนค่า จริง ไม่เช่นนั้น คืนค่า เท็จ

• ในขณะที่ฉัน <ขนาด A และ j> ขนาด B

  • ถ้าตัดกัน(A[i], B[i])

    • temp :=สูงสุดของ A[i, 0], B[j, 0], ต่ำสุดของ A[i,1] และ B[j, 1]

    • A[i,0] :=temp[1] + 1, B[j,0] :=temp[1] + 1

    • ถ้า A[i,0]> A[i,1] หรือ A[i,1] <=temp[0] ให้เพิ่ม i ขึ้น 1

    • ถ้า B[j,0]>B[j,1] หรือ B[j,1] <=temp[0]:ให้เพิ่ม j ขึ้น 1

    • result.append(ชั่วคราว)

    • ข้ามไปตอนต่อไป

  • ถ้า A[i,0]> B[j, 1] ให้เพิ่ม j ขึ้น 1 ไม่เช่นนั้น ให้เพิ่ม i ขึ้น 1

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

ตัวอย่าง

คลาส Solution(object):def intervalIntersection(self, A, B):result =[] i,j =0,0 while i  A[i][1] or A[i ][1] <=temp[0]:i+=1 if B[j][0]>B[j][1] or B[j][1] <=temp[0]:j+=1 result. ผนวก(ชั่วคราว) ดำเนินการต่อถ้า A[i][0]>B[j][1]:j+=1 อื่น:i+=1 ส่งคืนผลลัพธ์ def intersect(self,a,b):if a[0]<=b [0] และ a[1]>=b[0]:return True if b[0]<=a[0] and b[1]>=a[0]:return True return Falseob =Solution()print( ทางแยกช่วง([[0,2],[5,10],[13,23],[24,25]],[[1,5],[8,12],[15,24],[ 25,27]])))

อินพุต

ผลลัพธ์

[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]