LeetCode #57 Insert Interval: หมี มด เหยี่ยว แข่งแทรกช่วงเวลา

LeetCode #57 Insert Interval ให้รายการช่วงที่เรียงตามจุดเริ่มต้นและไม่มีช่วงทับกันอยู่แล้ว เราต้องแทรกช่วงใหม่หนึ่งช่วง รวมส่วนที่ชนกัน แล้วคืนรายการที่ยังเรียงและไม่ทับกัน โดยสร้างลิสต์ใหม่ได้ครับ ตามโจทย์ ช่วงที่แตะปลายกันอย่าง [1,2] กับ [2,3] ก็นับว่าทับกัน จึงต้องรวมเป็น [1,3]

ภาพใกล้ตัวคือตารางจองห้องประชุมที่รับนัดใหม่ แล้วรวบเวลาที่ชนกันให้เป็นช่วงเดียวเพื่อดูเวลาที่ห้องถูกใช้งาน

intervals = [[1,2], [5,7]], newInterval = [2,5]
→ [[1,7]]

วันนี้หมีตุ้ยนุ้ย มดจิ๋วแจ๋ว และเหยี่ยวตาคมจะมาถกกัน โดยมี บารอน สิงโตทะเลสวมเสื้อโค้ตเป็นกรรมการครับ

ผู้เข้าแข่งขัน

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
หมีตุ้ยนุ้ย	ต่อท้าย เรียงใหม่ แล้วรวมช่วง	ใจเย็น ชอบจัดของทั้งโต๊ะให้เรียบร้อยก่อน
มดจิ๋วแจ๋ว	เดินสามช่วง ก่อนชน / กำลังชน / หลังชน	ขยัน มีระเบียบ เดินไปข้างหน้าทีละก้าว
เหยี่ยวตาคม	ผ่าครึ่งหาขอบด้วย bisect แล้วประกอบลิสต์	มองตำแหน่งเป้าหมายก่อนลงมือ ไม่ไล่ตรวจทุกช่อง
บารอน	กรรมการ	เคาะโต๊ะด้วยครีบ ขอทั้งเหตุผลและเวลาที่วัดได้

วิธีที่ 1: หมีตุ้ยนุ้ย — ต่อท้ายแล้วเรียงใหม่

ตุ้ยนุ้ยยกกล่องนัดใหม่วางท้ายแถว “ผมจัดใหม่ทั้งแถวเลย จะได้ใช้วิธีรวมช่วงที่คุ้นมือ” เขาเรียงทุกช่วงตามจุดเริ่มต้น แล้วเดินอ่านจากซ้ายไปขวา ถ้าช่วงถัดไปเริ่มก่อนหรือเท่ากับปลายช่วงล่าสุด ก็ขยายปลายให้ไกลที่สุด มิฉะนั้นเปิดช่วงใหม่ในคำตอบ

เวลา: O(n log n) ในกรณีทั่วไป โดย n คือจำนวนช่วงเดิม สัญลักษณ์ O บอกแนวโน้มงานเมื่อข้อมูลโต ไม่ใช่เวลาหน่วยวินาที ส่วน log n หมายถึงจำนวนรอบที่โตช้าคล้ายการแบ่งข้อมูลครึ่งซ้ำ ๆ วิธีนี้มีทั้งงานเรียงและงานเดินรวมอีก O(n)
หน่วยความจำเพิ่ม: O(n) สำหรับลิสต์ที่เรียงและคำตอบ โค้ดสร้างคู่ตัวเลขใหม่ให้แต่ละกลุ่มที่ยังแยกกัน
ข้อดี: แยกขั้นตอนชัด และประยุกต์กับรายการที่ยังไม่เรียงได้ง่าย เหมาะเป็นคำตอบตั้งต้นให้ตรวจความเข้าใจ
ข้อเสีย/edge cases: โจทย์จัดลำดับมาให้แล้วจึงทำงานเรียงซ้ำ ต้องใช้ <= ตอนตรวจการทับกัน และต้องรับลิสต์ว่างได้โดยไม่หยิบสมาชิกตัวแรกทันที

วิธีที่ 2: มดจิ๋วแจ๋ว — เดินสามช่วง

จิ๋วแจ๋วไม่จัดแถวใหม่ เขาแบ่งการเดินเป็นสามตอน ตอนแรกเก็บช่วงที่จบก่อนนัดใหม่เริ่มลงคำตอบ ตอนที่สองรวมทุกช่วงที่เริ่มไม่เกินปลายของกลุ่มที่กำลังขยาย พอหมดส่วนที่ชนกันก็ใส่กลุ่มนั้นหนึ่งครั้ง แล้วต่อส่วนที่เหลือทั้งหมด

ของเดิม:    [1,2]   [4,6]   [8,10]   [13,15]
นัดใหม่:               [5--------9]
ก่อนชน:     [1,2]
รวมกลุ่ม:           [4----------10]
หลังชน:                               [13,15]
คำตอบ:      [1,2]   [4,10]             [13,15]

เงื่อนไขตอนแรกต้องเป็น end < start แบบเคร่งครัด เพราะจบเท่ากับจุดเริ่มใหม่ยังต้องรวมกัน ตอนที่สองจึงใช้ interval_start <= end และอัปเดต end หลังรวมทุกครั้ง ถ้านัดใหม่คลุมช่วงเดิมทั้งหมด เราจะอ่านส่วนที่ชนจนหมดแล้วได้คำตอบกลุ่มเดียว

เวลา: O(n) คือจำนวนงานโตตามจำนวนช่วง แต่ละช่วงผ่านการพิจารณาเพียงจำนวนครั้งคงที่ รวมงานต่อท้ายคำตอบด้วย
หน่วยความจำเพิ่ม: O(n) ในโค้ดนี้ ทั้งคำตอบและลิสต์ชั่วคราวจาก intervals[i:] การตัดลิสต์แบบนี้เรียกว่า slice และสร้างลิสต์ใหม่ ไม่ได้เป็นเพียงมุมมองของลิสต์เดิม
ข้อดี: เหตุผลตรงกับรูปช่วงเวลา ไม่ต้องเรียงซ้ำ และอธิบายความถูกต้องบนไวท์บอร์ดได้เป็นลำดับ
ข้อเสีย/edge cases: มีเงื่อนไขขอบสองแบบที่สลับผิดง่าย ต้องรองรับนัดใหม่อยู่หน้าสุด ท้ายสุด อยู่ในช่องว่าง และครอบทุกช่วง

วิธีที่ 3: เหยี่ยวตาคม — หาขอบด้วย bisect แล้วประกอบลิสต์

ตาคมบินขึ้นไปมองสองตำแหน่ง ใช้ binary search หรือการค้นหาที่ตัดตัวเลือกทิ้งทีละครึ่ง เพื่อหา left เป็นช่วงแรกที่ปลายไม่น้อยกว่าจุดเริ่มใหม่ และ right เป็นช่วงแรกที่จุดเริ่มมากกว่าปลายใหม่ ดังนั้นช่วงเดิมที่ต้องรวมอยู่ในตำแหน่ง left จนถึงก่อน right

ใช้ bisect กับ key= ซึ่งมีตั้งแต่ Python 3.10 เพื่อเลือกเปรียบเทียบปลายหรือจุดเริ่ม ส่วนค่าค้นหาเป็นตัวเลขขอบเขตครับ

การค้นหาตามปลายช่วงทำได้ เพราะเงื่อนไขของโจทย์รับประกันทั้งการเรียงและการไม่ทับกัน ปลายช่วงจึงเรียงตามกันด้วย ถ้ามีช่วงซ้อนอยู่ภายในกัน ข้อสรุปนี้ใช้ไม่ได้ และห้ามนำวิธีนี้ไปใช้โดยไม่ตรวจเงื่อนไขข้อมูลก่อน

ถ้า left < right ให้ขยายขอบจากช่วงแรกและช่วงสุดท้ายในกลุ่ม ถ้าเท่ากัน แปลว่าไม่มีช่วงเดิมต้องรวม จากนั้น splice หรือประกอบลิสต์ด้วยส่วนหน้า กลุ่มใหม่ และส่วนท้าย ไม่ต้องเพิ่มช่วงใหม่แล้วเรียกการแทรกซ้ำหลายครั้ง

เหยี่ยวใช้ปลายของนัดใหม่เดิมหา right ได้เลย ไม่ต้องค้นหาใหม่หลังขยาย เพราะช่วงเดิมไม่ทับกัน หากช่วงสุดท้ายที่รวมยาวเกินปลายใหม่ ช่วงถัดจากมันก็ต้องเริ่มหลังปลายของมันอยู่แล้ว จึงไม่มีช่วงที่ต้องลากเข้ามารวมเพิ่ม

เวลา: ค้นหาสองขอบ O(log n) แต่คัดลอกสมาชิกเพื่อสร้างคำตอบยัง O(n) ในกรณีเลวร้ายที่สุด เวลารวมจึงเป็น O(n) ไม่ใช่ O(log n)
หน่วยความจำเพิ่ม: O(n) สำหรับคำตอบและลิสต์ชั่วคราวจาก slice และการต่อด้วย + ซึ่งอาจสร้างลิสต์ผ่านกลางหลายชุด
ข้อดี: ลดการวนตรวจทีละช่วงใน Python ได้มาก โดยเฉพาะเมื่อกลุ่มที่ทับกันมีขนาดใหญ่ และการคัดลอกลิสต์ส่วนใหญ่ทำโดยตัว interpreter
ข้อเสีย/edge cases: ต้องเลือก bisect_left กับ bisect_right ให้ตรงเครื่องหมายเท่ากับ และต้องใช้ข้อมูลเรียงที่ไม่ทับกันเท่านั้น

ทั้งสามวิธีไม่ได้แก้ลิสต์เดิมโดยตรง จึงไม่ใช่ in-place หรือการแก้ข้อมูลในที่เดิมโดยใช้พื้นที่ช่วยเพียงเล็กน้อย

โค้ดทุกวิธี พร้อมเทสต์

บันทึกเป็น solution.py แล้วรัน python3 -I -B solution.py ครับ ALL ใช้เทสต์เดียวกันกับสัตว์ทุกตัว พร้อมตรวจว่าไม่แก้ข้อมูลเข้า

เทสต์ค่าซ้ำใช้กรณีนัดใหม่ตรงกับช่วงเดิม ค่าติดลบช่วยตรวจตรรกะเปรียบเทียบ ส่วนเคสสุ่มคูณพิกัดด้วยสองเพื่อใช้ชุดจุดตรวจพื้นที่และช่องว่างของคำตอบ

import bisect
import platform
import random
import timeit
import unittest


def bear(intervals, new_interval):
    ordered = sorted(intervals + [new_interval], key=lambda item: item[0])
    result = []
    for start, end in ordered:
        if result and start <= result[-1][1]:
            result[-1] = [result[-1][0], max(result[-1][1], end)]
        else:
            result.append([start, end])
    return result


def ant(intervals, new_interval):
    result = []
    i = 0
    start, end = new_interval
    while i < len(intervals) and intervals[i][1] < start:
        result.append(intervals[i])
        i += 1
    while i < len(intervals) and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])
    result.extend(intervals[i:])
    return result


def hawk(intervals, new_interval):
    start, end = new_interval
    left = bisect.bisect_left(intervals, start, key=lambda item: item[1])
    right = bisect.bisect_right(intervals, end, key=lambda item: item[0])
    if left < right:
        start = min(start, intervals[left][0])
        end = max(end, intervals[right - 1][1])
    return intervals[:left] + [[start, end]] + intervals[right:]


ALL = [bear, ant, hawk]


def run_benchmark():
    print(platform.python_version(), platform.machine())
    for n, number in [(1_000, 100), (100_000, 5)]:
        intervals = [[4 * i, 4 * i + 1] for i in range(n)]
        new_interval = [4 * (n // 3), 4 * (2 * n // 3) + 1]
        expected = ant(intervals, new_interval)
        for fn in ALL:
            assert fn(intervals, new_interval) == expected
            samples = timeit.repeat(
                lambda: fn(intervals, new_interval), repeat=5, number=number
            )
            print(n, fn.__name__, f'{min(samples) / number * 1_000:.3f}')


class InsertIntervalTests(unittest.TestCase):
    def check_all(self, intervals, new_interval, expected):
        for fn in ALL:
            with self.subTest(method=fn.__name__, data=intervals):
                original = [item[:] for item in intervals]
                new_copy = new_interval[:]
                self.assertEqual(fn(intervals, new_interval), expected)
                self.assertEqual(intervals, original)
                self.assertEqual(new_interval, new_copy)

    def test_examples_and_edges(self):
        cases = [
            ([], [2, 3], [[2, 3]]),
            ([[1, 3]], [2, 5], [[1, 5]]),
            ([[1, 2], [5, 7]], [-3, -1], [[-3, -1], [1, 2], [5, 7]]),
            ([[1, 2]], [4, 5], [[1, 2], [4, 5]]),
            ([[1, 2], [5, 7]], [0, 9], [[0, 9]]),
            ([[1, 2], [5, 7]], [3, 4], [[1, 2], [3, 4], [5, 7]]),
            ([[1, 2], [5, 7]], [2, 5], [[1, 7]]),
            ([[1, 3]], [1, 3], [[1, 3]]),
            ([[2, 2]], [2, 2], [[2, 2]]),
            ([[1, 8]], [3, 4], [[1, 8]]),
            ([[-8, -5], [-2, 1]], [-6, -1], [[-8, 1]]),
            ([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]],
             [4, 8], [[1, 2], [3, 10], [12, 16]]),
        ]
        for intervals, new_interval, expected in cases:
            self.check_all(intervals, new_interval, expected)

    def test_random_against_integer_points(self):
        rng = random.Random(57)
        for _ in range(200):
            points = sorted(rng.sample(range(-30, 31), rng.randrange(0, 8) * 2))
            intervals = [points[i:i + 2] for i in range(0, len(points), 2)]
            new_interval = sorted(rng.sample(range(-35, 36), 2))
            # Scale by two so a real gap stays visible between integer points.
            covered = set()
            for start, end in intervals + [new_interval]:
                covered.update(range(2 * start, 2 * end + 1))
            for fn in ALL:
                result = fn(intervals, new_interval)
                actual = set()
                for start, end in result:
                    self.assertLessEqual(start, end)
                    actual.update(range(2 * start, 2 * end + 1))
                self.assertEqual(actual, covered)
                self.assertTrue(all(a[1] < b[0] for a, b in zip(result, result[1:])))


if __name__ == "__main__":
    unittest.main()

มดกับเหยี่ยวอาจใช้คู่ช่วงเดิมร่วมกับผลลัพธ์ในส่วนที่ไม่เปลี่ยน การเรียกฟังก์ชันไม่แก้ข้อมูลเข้า แต่ถ้าผู้เรียกนำผลไปแก้คู่ย่อยภายหลัง อาจกระทบต้นฉบับได้ ถ้าต้องการแยกข้อมูลทุกคู่จริง ๆ ให้คัดลอกเพิ่ม และวัดต้นทุนของเงื่อนไขนั้นใหม่ด้วยครับ

Benchmark ที่รันจริง (23 ต.ค. 2026 บนเครื่องนี้)

รันด้วย python3 -I -B ใช้ Python 3.14.7 จาก python3 -V และสถาปัตยกรรม x86_64 จาก platform.machine() ผมใช้ timeit.repeat วัดห้าชุด เลือกชุดที่เร็วที่สุด แล้วหารจำนวนครั้งในชุดให้เป็นเวลาต่อหนึ่งการเรียก

สร้างช่วงเดิมเป็น [4*i, 4*i+1] สำหรับ i ตั้งแต่ศูนย์ถึงก่อน n และนัดใหม่เป็น [4*(n//3), 4*(2*n//3)+1] จึงรวมกลุ่มตรงกลางประมาณหนึ่งในสามของรายการ แต่ละชุดเรียก 100 ครั้งสำหรับ n = 1,000 และ 5 ครั้งสำหรับ n = 100,000 การสร้างข้อมูลและตรวจคำตอบอยู่นอกส่วนจับเวลา ส่วนการสร้างลิสต์ผลลัพธ์อยู่ในเวลาที่วัด

วิธี	n = 1,000 (ms/ครั้ง)	n = 100,000 (ms/ครั้ง)
หมี: ต่อท้าย เรียง แล้วรวม	0.086	10.816
มด: เดินสามช่วง	0.049	4.775
เหยี่ยว: bisect แล้วประกอบลิสต์	0.004	0.742

เหยี่ยวชนะชุดนี้เพราะค้นหาขอบด้วยการเปรียบเทียบไม่กี่รอบ และใช้การคัดลอกลิสต์แทนการเดินรวมกลุ่มตรงกลางทีละช่วงใน Python มดประหยัดงานเรียงของหมี ส่วนหมีมีทั้งการเดินรวมและสร้างคู่ใหม่หลายคู่ แม้การเรียงของ Python จะได้ประโยชน์จากข้อมูลที่เกือบเรียงอยู่แล้ว ตัวเลขนี้เป็นของเครื่องนี้และรูปข้อมูลนี้เท่านั้น การเปลี่ยนตำแหน่งนัดใหม่หรือสัดส่วนที่ทับกันอาจเปลี่ยนอันดับได้ จึงไม่ควรอ่านผลเป็นคำรับประกันความเร็วทั่วไป

วัดซ้ำด้วย python3 -I -B -c 'import runpy; runpy.run_path("solution.py")["run_benchmark"]()'

ตารางเลือกวิธีตามสถานการณ์

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด	มดจิ๋วแจ๋ว	อธิบายสามช่วงและเหตุผลที่หยุดรวมได้ตรงไปตรงมา
โค้ดงานจริงที่เป็น hot path (production)	เหยี่ยวตาคม เมื่อวัดกับข้อมูลจริงแล้ว	hot path คือส่วนที่ถูกเรียกบ่อย ชุดวัดนี้ชนะชัด แต่ต้องยืนยันกับงานจริง
สอนมือใหม่	หมีตุ้ยนุ้ย แล้วค่อยต่อด้วยมด	เห็นขั้นเรียงกับขั้นรวมแยกกัน ก่อนใช้ประโยชน์จากข้อมูลที่เรียงมาแล้ว
หน่วยความจำจำกัด	แนวมด แต่เปลี่ยนการต่อท้ายเป็นวนเพิ่มทีละช่วง	ลดลิสต์ชั่วคราวจาก slice ได้ แม้ยังต้องเก็บคำตอบ และต้องวัดโค้ดที่ปรับใหม่
รับข้อมูลทีละช่วงตามลำดับ	แนวมด	เดินไปข้างหน้าได้ ไม่ต้องกระโดดอ่านตำแหน่งกลางเหมือน bisect
รายการไม่เรียง หรือช่วงเดิมทับกันได้	หมีตุ้ยนุ้ย	เรียงและรวมทั้งหมดก่อน ทำให้รองรับข้อมูลที่กว้างกว่ากติกาข้อนี้

ค่าเริ่มต้นภายใต้กติกาของโจทย์: มดจิ๋วแจ๋วสำหรับคำตอบที่อธิบายง่ายและเวลา O(n); เลือกเหยี่ยวเมื่อใช้ Python 3.10 ขึ้นไปและผลวัดของงานรองรับการตัดสินใจ

บารอนสรุป

บารอนกระชับเสื้อโค้ตแล้วเคาะครีบ “สนามนี้เหยี่ยวรับถ้วยเวลาไป ทั้งรายการเล็กและใหญ่มีตัวเลขยืนยันครับ” เขาหันไปหามด “แต่ถ้าต้องเขียนให้เพื่อนเข้าใจบนกระดาน ผมให้เจ้าขึ้นก่อน เพราะใช้กติกาที่เรียงมาแล้วอย่างตรงไปตรงมา” ส่วนหมีได้คำชมว่ารับข้อมูลที่ยังไม่พร้อมได้กว้างกว่า แต่เสียงานจัดแถวซ้ำภายใต้โจทย์นี้ บารอนปิดสมุดว่า “อย่าตัดสินจากชื่อ binary search อย่างเดียว การคืนลิสต์ยังมีต้นทุน และทุกตัวต้องรวมช่วงที่แตะปลายให้ถูกก่อนคุยเรื่องเร็วครับ”

Recap

เขียนเงื่อนไขว่าช่วงแตะปลายต้องรวม แล้วลอง [1,2] กับ [2,3]
วาดสามส่วนของมด พร้อมระบุว่าตัวแปรปลายขวาขยายตอนไหน
อธิบายให้ได้ว่าทำไมปลายช่วงเดิมจึงเรียงตามกันภายใต้กติกานี้
ตรวจตำแหน่ง left และ right ของเหยี่ยวในกรณีไม่มีช่วงทับกัน
รันเทสต์ทั้งลิสต์ว่าง นัดหน้าสุด ท้ายสุด และนัดที่ครอบทั้งหมด
วัดข้อมูลรูปแบบงานจริง แล้วนับต้นทุนการสร้างคำตอบรวมด้วย