การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน
จัดตารางโดยเลือกช่วงที่สิ้นสุดเร็วที่สุดแบบโลภ
การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เป้าหมายของการนำออก
คุณมีช่วงที่ทับซ้อนกันและต้องการ นำออกให้น้อยที่สุด เพื่อไม่ให้มีช่วงใดทับซ้อนกันอีกต่อไป ให้เก็บช่วงไว้ให้ได้มากที่สุด ✂️
กลับมุมมองของโจทย์
การนำออกให้น้อยที่สุดก็เหมือนกับการ เก็บช่วงที่ไม่ทับซ้อนกันไว้ให้ได้มากที่สุด แก้โจทย์ในรูปแบบการเก็บไว้ แล้วจำนวนที่นำออกคือ n ลบด้วยจำนวนที่เก็บไว้
นี่คือการเลือกกิจกรรม
การเก็บช่วงที่ไม่ทับซ้อนกันไว้ให้ได้มากที่สุดก็คือโจทย์การเลือก กิจกรรมแบบคลาสสิกในอีกรูปแบบหนึ่ง แนวคิดแบบละโมบเดียวกันนี้ใช้แก้โจทย์ทั้งสองแบบได้
sort ตามเวลาสิ้นสุด
ลำดับที่เหมาะสมในที่นี้คือเรียงตามเวลา สิ้นสุด ไม่ใช่เวลาเริ่มต้น การเสร็จสิ้นเร็วจะเปิดพื้นที่บนเส้นเวลาให้ช่วงถัดไปที่คุณอาจเก็บไว้ได้เร็วที่สุด
intervals.sort(key=lambda x: x[1])ตัวเลือกแบบละโมบ
ให้เก็บช่วงที่ สิ้นสุดเร็วที่สุดเสมอในบรรดาช่วงที่ยังเข้ากันได้ ช่วงนี้จะเหลือพื้นที่ให้ส่วนที่เหลือมากที่สุด
ติดตามจุดสิ้นสุดล่าสุดที่เก็บไว้
เก็บจุดสิ้นสุดของช่วงล่าสุดที่คุณเก็บไว้ ช่วงถัดไปจะเข้ากันได้ก็ต่อเมื่อจุดเริ่มต้นอยู่ที่หรือหลัง ขอบเขตนั้น
if start >= last_end:
last_end = endนับจำนวนที่นำออก
เมื่อช่วงหนึ่งเริ่มต้นก่อน last_end ช่วงนั้นจะขัดแย้งกัน ดังนั้นให้ ทิ้งช่วงนั้นและเพิ่มจำนวนการนำออกหนึ่งรายการ มิฉะนั้นให้เก็บช่วงนั้นไว้
else:
removed += 1เหตุผลที่จุดสิ้นสุดเร็วที่สุดชนะ
พิสูจน์ได้ด้วยการสลับ: การสลับช่วงที่เก็บไว้กับช่วงที่เข้ากันได้และสิ้นสุดเร็วที่สุดจะไม่ทำให้จำนวนช่วงที่เก็บไว้ได้ลดลง
จัดการกรณีปลายช่วงแตะกัน
โปรดตัดสินใจว่า [1, 2] และ [2, 3] ถือว่าทับซ้อนกันหรือไม่ หากอนุญาตให้ใช้จุดปลายร่วมกันได้ ให้ใช้ start >= last_end เป็นการทดสอบ
กระบวนการแบบละโมบทั้งหมด
sort ตามเวลาสิ้นสุด กวาดหนึ่งครั้ง และนับความขัดแย้ง เวลารวมคือ O(n log n) จากการ sort และการวนผ่านเชิงเส้นเพียงครั้งเดียว
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1รูปแบบที่คุ้นเคย
รูปแบบนี้ใช้จัดตารางการประชุมให้ได้มากที่สุดในห้องเดียว หรือจัดงานให้ได้มากที่สุดบนเครื่องจักรเดียว โปรดนึกถึงรูปแบบนี้เมื่อจำเป็นต้อง ลดความขัดแย้งให้เหลือน้อยที่สุด
ตรวจสอบอย่างรวดเร็ว
คุณเก็บช่วงที่ไม่ทับซ้อนกันไว้ด้วยวิธีแบบละโมบ
สรุป
จำนวนการนำออกขั้นต่ำเท่ากับ n ลบด้วยจำนวนช่วงที่คุณสามารถ เก็บไว้ได้มากที่สุด sort ตามเวลาสิ้นสุด เก็บช่วงที่เข้ากันได้และสิ้นสุดเร็วที่สุดแบบละโมบ แล้วนับช่วงที่เหลือ 🚀
คำถามที่พบบ่อย
บทเรียน “การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน”
จัดตารางโดยเลือกช่วงที่สิ้นสุดเร็วที่สุดแบบโลภ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- เรียงช่วงตามจุดเริ่มต้น
- ผสานช่วงที่ทับซ้อนกัน
- กวาดเส้นเพื่อหาการทับซ้อนสูงสุด
- การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน