รวมช่วงเวลาที่ทับซ้อนกันโดยใช้ C ++

คำชี้แจงปัญหา

กำหนดชุดของช่วงเวลาในลำดับใด ๆ ให้รวมช่วงเวลาที่ทับซ้อนกันทั้งหมดเป็นหนึ่งและส่งออกผลลัพธ์ซึ่งควรมีเฉพาะช่วงเวลาที่ไม่เกิดร่วมกันเท่านั้น

ช่วงที่กำหนดคือ {{12, 14}, {11, 13}, {20, 22}, {21, 23}} จากนั้น

ช่วงเวลา {12, 14} และ {11, 13} ทับซ้อนกัน จึงรวมเป็น {11, 14}
ช่วงเวลา {20, 22} และ {21, 23} ทับซ้อนกัน จึงรวมเป็น {20, 23}

อัลกอริทึม

<ก่อน>1. จัดเรียงช่วงเวลาตามลำดับที่เพิ่มขึ้นของเวลาเริ่มต้น2 ผลักช่วงเวลาแรกไปที่ stack3 สำหรับแต่ละช่วงให้ทำตามขั้นตอนด้านล่าง:3.1 หากช่วงเวลาปัจจุบันไม่ทับซ้อนกับด้านบนของสแต็ก ให้กด 3.2. หากช่วงเวลาปัจจุบันทับซ้อนกับด้านบนของสแต็กและเวลาสิ้นสุดของช่วงเวลาปัจจุบันมากกว่าด้านบนของสแต็ก ให้อัปเดตส่วนบนของสแต็กด้วยเวลาสิ้นสุดของช่วงเวลาปัจจุบัน4 สุดท้าย สแต็กมีช่วงเวลาที่ผสาน

ตัวอย่าง

#include #include #include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) โดยใช้ namespace std;struct interval { int start; int end;};bool comparisonInterval (ช่วง i1, ช่วง i2) { return (i1.start  s; sort(arr, arr + n, ช่วงเวลาเปรียบเทียบ); s.push(arr[0]); สำหรับ (int i =1; i  ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 ช่วงเวลาที่ผสาน:{20, 23} {11, 14}