กวาดเส้นเพื่อหาการทับซ้อนสูงสุด
นับช่วงที่เกิดขึ้นพร้อมกันด้วยเหตุการณ์
กวาดเส้นเพื่อหาการทับซ้อนสูงสุด เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คำถามเรื่องการทับซ้อนสูงสุด
มีช่วงกี่ช่วงที่ครอบคลุมช่วงเวลาเดียวกันพร้อมกัน จำนวนสูงสุดคือการทับซ้อน สูงสุด ซึ่งเป็นจุดที่หนาแน่นที่สุดบนเส้นเวลา 📈
คิดเป็นเหตุการณ์
หยุดคิดถึงช่วงทั้งหมด ให้แยกแต่ละช่วงออกเป็น เหตุการณ์สองรายการ: ค่า +1 เมื่อเริ่มต้น และค่า -1 เมื่อสิ้นสุด
สร้างรายการเหตุการณ์
สำหรับทุกช่วง ให้เพิ่มเหตุการณ์เริ่มต้นและเหตุการณ์สิ้นสุดลงใน รายการเดียวกัน แต่ละเหตุการณ์จะเก็บตำแหน่งและค่าเดลตาเป็นบวกหรือลบหนึ่ง
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))เรียงลำดับเหตุการณ์
ให้ sort เหตุการณ์ทุกเหตุการณ์ตาม ตำแหน่ง เพื่อให้คุณกวาดไปตามเส้นเวลาจากซ้ายไปขวาและประมวลผลการเปลี่ยนแปลงตามลำดับที่ถูกต้อง
events.sort()กวาดและนับ
ไล่ดูเหตุการณ์ที่เรียงลำดับแล้ว พร้อมรักษา ตัวนับสะสมไว้ เพิ่มค่าเดลตาแต่ละค่าขณะไล่ผ่าน แล้วตัวนับจะแสดงว่าขณะนี้มีช่วงที่ใช้งานอยู่กี่ช่วง
active = 0
for pos, delta in events:
active += deltaติดตามค่าสูงสุด
หลังการอัปเดตแต่ละครั้ง ให้เปรียบเทียบตัวนับกับค่าที่ดีที่สุดจนถึงตอนนั้น ค่าสูงสุดที่ตัวนับเคยไปถึงคือการทับซ้อน สูงสุด
best = max(best, active)เคล็ดลับการจัดการกรณีค่าเท่ากัน
เมื่อมีตำแหน่งเท่ากัน ลำดับมีความสำคัญ หากการสิ้นสุดที่ x ควรปล่อยช่องว่างก่อนการเริ่มต้นที่ x ให้เรียงจุดสิ้นสุดไว้ ก่อนจุดเริ่มต้นที่ตำแหน่งเดียวกัน
เข้ารหัสค่าเดลตาเพื่อเรียงลำดับให้ถูกต้อง
วิธีที่เรียบร้อยในการจัดการค่าที่เท่ากันคือเลือกค่าเดลตาให้การเรียงลำดับทูเพิลจัดการให้เอง วางค่า เดลตา -1 ไว้ก่อน +1 เมื่อมีตำแหน่งเดียวกัน
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tieเหตุผลที่รวดเร็ว
คุณสร้างเหตุการณ์ 2n รายการ เรียงลำดับหนึ่งครั้ง และกวาดหนึ่งครั้ง วิธีทั้งหมดจึงใช้เวลา O(n log n) โดยมีการ sort เพียงครั้งเดียวเป็นส่วนที่ใช้เวลามากที่สุด
พบรูปแบบนี้ที่ไหน
การทับซ้อนสูงสุดช่วยตอบโจทย์คลาสสิก เช่น จำนวน ห้องขั้นต่ำที่ต้องใช้สำหรับการประชุม หรือจำนวนผู้ใช้พร้อมกันสูงสุดบนเซิร์ฟเวอร์
มากกว่าการนับเพียงอย่างเดียว
คุณสามารถต่อยอดการกวาดแบบเดียวกันได้ง่าย ๆ เช่น ติดตามความยาวรวมที่ถูกครอบคลุม หรือค้นหาทุกตำแหน่งที่ จำนวนเปลี่ยนแปลง ทั้งหมดนี้ทำได้ในการวนผ่านเชิงเส้นเพียงครั้งเดียว
ตรวจสอบอย่างรวดเร็ว
คุณกวาดเหตุการณ์เพื่อหาการทับซ้อนสูงสุด
สรุป
เปลี่ยนช่วงให้เป็น เหตุการณ์เริ่มต้น +1 และเหตุการณ์สิ้นสุด -1 เรียงลำดับ แล้วกวาดตัวนับเพื่อหาค่าสูงสุด จัดการค่าที่เท่ากันโดยให้สิ้นสุดก่อนเริ่มต้น 🚀
คำถามที่พบบ่อย
บทเรียน “กวาดเส้นเพื่อหาการทับซ้อนสูงสุด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “กวาดเส้นเพื่อหาการทับซ้อนสูงสุด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ 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 ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “กวาดเส้นเพื่อหาการทับซ้อนสูงสุด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- เรียงช่วงตามจุดเริ่มต้น
- ผสานช่วงที่ทับซ้อนกัน
- กวาดเส้นเพื่อหาการทับซ้อนสูงสุด
- การลบน้อยที่สุดเพื่อไม่ให้ทับซ้อน