Chương 14 - Interval

Interval (khoảng [start, end]) là pattern bao trùm nhiều bài calendar/scheduling/booking quan trọng. Hai chương 4 (Sorting) đã chạm qua Merge Intervals và Meeting Rooms II; chương này xoáy sâu vào 8 mẫu thao tác trên interval (merge, insert, intersection, overlap, free time) - đây là pattern không thể tránh khi phỏng vấn các công ty lịch (Google Calendar) và đặt phòng (Airbnb, Booking).

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Quy ước open/closed: [s, e] (closed) vs [s, e) (half-open) ảnh hưởng < vs <=.
  • Sort theo start cho merge; sort theo end cho greedy chọn nhiều nhất.
  • Sweep line idiom: events (time, +1/-1) → đếm overlap tối đa.
  • Tie-break rule: end trước start (giải phóng resource trước khi xin mới).

Khi nào dùng pattern này?

  • Input là các khoảng [start, end] (booking, meeting, video segment, …).
  • Cần trả lời: gộp / chèn / cắt / đếm overlap / free time.
  • Mọi bài interval đều bắt đầu bằng sort theo start (hoặc end).

4 thao tác chuẩn trên 2 interval A = [a₁, a₂], B = [b₁, b₂]:

1. Tách rời (disjoint):   A.end < B.start  →  A trước B, không giao
2. Chạm điểm (touch):     A.end == B.start →  liền kề, có thể merge tuỳ đề
3. Giao một phần:         A.start < B.start ≤ A.end < B.end
4. Chứa nhau (contain):   A.start ≤ B.start ≤ B.end ≤ A.end

Template code 

from typing import List

# 1) Merge 2 interval có giao nhau
def merge_two(a, b):
    return [min(a[0], b[0]), max(a[1], b[1])]


# 2) Check overlap (kể cả chỉ chạm điểm)
def overlaps(a, b) -> bool:
    return a[0] <= b[1] and b[0] <= a[1]


# 3) Sweep line: cùng pattern cho mọi bài "đếm overlap tối đa"
events: List[tuple[int, int]] = []
for s, e in intervals:
    events.append((s, +1))       # mở
    events.append((e, -1))       # đóng
events.sort()
cur = peak = 0
for _, delta in events:
    cur += delta
    peak = max(peak, cur)

Bài tự luyện cuối chương

  • LC 252 - Meeting Rooms (chỉ check có overlap)
  • LC 986 - Interval List Intersections
  • LC 1851 - Minimum Interval to Include Each Query
  • LC 763 - Partition Labels (Chương 16)
  • LC 1288 - Remove Covered Intervals

14.1 Merge Intervals (LC 56) - recap

Đã giải đầy đủ ở Chương 4.2 dưới góc Sorting. Ở đây mình tóm tắt nhanh dưới lens “interval” và mở rộng follow-up.

Đề bài

Gộp các khoảng giao nhau. [1,3] và [2,6] → [1,6].

Hướng tiếp cận

Sort theo start. Duyệt 1 lượt, giữ last = interval cuối đã thêm vào kết quả. Nếu cur.start <= last.end → last.end = max(last.end, cur.end); ngược lại push cur mới.

Code Python 3 

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        result = []
        for cur in intervals:
            if result and cur[0] <= result[-1][1]:
                result[-1][1] = max(result[-1][1], cur[1])
            else:
                result.append(cur[:])
        return result

Phân tích độ phức tạp

  • Thời gian: O(n log n) (sort dominate).
  • Bộ nhớ: O(n) output.

Bình luận thêm cho góc interval

  • Stream version: thêm interval mới vào output đã merge → dùng binary search tìm vị trí + merge 2 chiều. Pattern này áp cho MyCalendarThree (LC 732).
  • Multi-list version: Merge intervals từ N người (N

    1) - dùng heap.

Bài tự luyện liên quan

  • LC 57 - Insert Interval (bài 14.2).
  • LC 252, 253 - Meeting Rooms (I, II).
  • LC 715 - Range Module.

14.2 Insert Interval (LC 57)

Đề bài

Cho mảng intervals đã sort theo start và không giao nhau. Chèn newInterval vào và merge nếu cần.

Ví dụ 

Input:  intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Input:  intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Ràng buộc

  • 0 <= len(intervals) <= 10^4

Clarifying questions

  • intervals rỗng? → Trả [newInterval].
  • newInterval phủ toàn bộ? → Merge thành 1 interval.

Hướng tiếp cận

Cách 1 - O(n) duyệt 1 lượt, 3 giai đoạn.

  1. Trước newInterval: đẩy hết các interval có end < newInterval.start.
  2. Giao nhau: với các interval có start <= newInterval.end, mở rộng newInterval (start = min, end = max). Cuối giai đoạn, push newInterval.
  3. Sau newInterval: đẩy phần còn lại.

Cách 2 - Concat + merge (gọi lại bài 14.1). Đơn giản nhưng O(n log n) cho sort thừa.

Hình minh hoạ với intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4,8]:

Trục số:
1   3   5   6  7  8  10        12      16
├─┤ ├───┤ ├─┤  ├──┤            ├──────┤
        ├──────────┤  new = [4, 8]

Giai đoạn 1 (end < 4):  [1, 2]
                         result = [[1,2]]

Giai đoạn 2 (start <= 8):
  [3, 5]: mở rộng newInterval = [min(4,3), max(8,5)] = [3, 8]
  [6, 7]: mở rộng = [3, 8]
  [8, 10]: mở rộng = [3, 10]
  Push [3, 10]
                         result = [[1,2], [3,10]]

Giai đoạn 3: còn [12, 16]
                         result = [[1,2], [3,10], [12,16]]  ✓

Code Python 3 

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        i, n = 0, len(intervals)
        # 1) Trước newInterval.
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        # 2) Giao nhau - mở rộng newInterval.
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)
        # 3) Sau newInterval.
        while i < n:
            result.append(intervals[i])
            i += 1
        return result

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(n) cho output.

Bình luận

  • Tận dụng input đã sort → O(n). Nếu input không sort, sort trước rồi gọi bài 14.1 - O(n log n).
  • Bẫy < vs <=: điều kiện giao là intervals[i][0] <= newInterval[1]. Dấu = ở đây quan trọng - đề LC 56/57 coi 2 interval chạm điểm là giao.

Bài tự luyện liên quan

  • LC 56 - Merge Intervals.
  • LC 715 - Range Module.

14.3 Non-overlapping Intervals (LC 435)

Đề bài

Cho mảng intervals. Trả về số interval tối thiểu cần xoá để các interval còn lại không giao nhau.

Ví dụ 

Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Giải thích: xoá [1,3] → còn [1,2],[2,3],[3,4] không giao nhau.

Input:  intervals = [[1,2],[1,2],[1,2]]
Output: 2

Input:  intervals = [[1,2],[2,3]]
Output: 0              (đã không giao, không cần xoá)

(mỗi phần tử [start, end] biểu diễn khoảng nửa-mở [start, end))

Ràng buộc

  • 1 <= len(intervals) <= 10^5
  • -5·10^4 <= start, end <= 5·10^4

Clarifying questions

  • Tie ở end (cùng end)? → Sort theo end; nếu end bằng nhau, thứ tự không quan trọng cho count.

Hướng tiếp cận

Greedy - sort theo end tăng dần. Giữ interval có end nhỏ nhất → giữ được càng nhiều “không gian” về sau cho các interval tiếp theo.

Pseudocode: - Sort theo end. - Giữ last_end = -∞. Với mỗi interval [s, e]: - Nếu s >= last_end → giữ (không overlap), last_end = e. - Ngược lại → đếm xoá.

Tại sao sort theo end, không phải start? Greedy hoạt động vì: “luôn chọn interval có end sớm nhất” cho phép phần còn lại có nhiều “free time” hơn - chứng minh quy nạp.

Hình minh hoạ với [[1,2],[2,3],[3,4],[1,3]]:

Sort theo end:  [[1,2], [2,3], [1,3], [3,4]]
                       end=2   end=3   end=3   end=4

Duyệt:
  [1,2]: start=1 >= -inf → giữ; last_end=2          giữ: 1
  [2,3]: start=2 >= 2    → giữ; last_end=3          giữ: 2
  [1,3]: start=1 < 3     → xoá                       xoá: 1
  [3,4]: start=3 >= 3    → giữ; last_end=4          giữ: 3

Giữ 3, xoá 1 → đáp án = 1.

Code Python 3 

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        kept = 1
        last_end = intervals[0][1]
        for s, e in intervals[1:]:
            if s >= last_end:
                kept += 1
                last_end = e
        return len(intervals) - kept

Phân tích độ phức tạp

  • Thời gian: O(n log n). Bộ nhớ: O(1) hoặc O(n) cho sort.

Bình luận

  • Đây là bài Greedy kinh điển - cùng pattern với Activity Selection (Chương 16).
  • Bẫy sort: sort theo start có thể work nếu xử lý cẩn thận (giữ interval có end nhỏ hơn khi có conflict). Nhưng sort theo end là cách đơn giản nhất.

Bài tự luyện liên quan

  • LC 452 - Minimum Number of Arrows to Burst Balloons (bài 14.5).
  • LC 1326 - Minimum Number of Taps to Open (Chương 39).
  • LC 1235 - Maximum Profit in Job Scheduling.

14.4 Meeting Rooms II (LC 253) - recap

Đã giải đầy đủ ở Chương 4.4. Ở đây chỉ tóm tắt và liên hệ.

Đề bài

Tìm số phòng tối thiểu để chứa tất cả meeting.

Hướng tiếp cận

3 cách (heap, sweep line events, chronological 2-pointer) - tất cả đều O(n log n). Sweep line là pattern interval ngôn ngữ chuẩn.

Code Python 3 

from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = [(s, +1) for s, _ in intervals] + [(e, -1) for _, e in intervals]
        events.sort(key=lambda x: (x[0], x[1]))
        cur = peak = 0
        for _, d in events:
            cur += d
            peak = max(peak, cur)
        return peak

Phân tích độ phức tạp

  • Thời gian: O(n log n).
  • Bộ nhớ: O(n).

Bình luận thêm

  • Bài này là cốt lõi cho mọi “max concurrent X”:
    • LC 218 (Skyline): event = building start/end với chiều cao.
    • LC 1094 (Car Pooling): event = pickup/dropoff với số passenger.
  • Xem giải đầy đủ tại 4.4.

Bài tự luyện liên quan

  • LC 218 - The Skyline Problem.
  • LC 1094 - Car Pooling.
  • LC 759 - Employee Free Time (bài 14.6).

14.5 Minimum Number of Arrows to Burst Balloons (LC 452)

Đề bài

Cho mảng các balloon [x_start, x_end] (mỗi balloon là 1 interval trên trục x). Một mũi tên bắn thẳng đứng tại x = X sẽ làm nổ tất cả balloon có x_start <= X <= x_end. Tìm số mũi tên tối thiểu để nổ hết.

Ví dụ 

Input:  points = [[10,16],[2,8],[1,6],[7,12]]
        (mỗi phần tử [xstart, xend] biểu diễn 1 quả bóng nằm trong khoảng đóng [xstart, xend])
Output: 2   (cần ít nhất 2 mũi tên: bắn x=6 nổ [1,6] và [2,8]; bắn x=11 nổ [7,12] và [10,16])
Giải thích:
  1 mũi tại x = 6 nổ [1,6] và [2,8].
  1 mũi tại x = 11 nổ [7,12] và [10,16].

Ràng buộc

  • 1 <= len(points) <= 10^5
  • -2^31 <= x_start <= x_end <= 2^31-1

Clarifying questions

  • Không có balloon? → Trả 0.
  • Tất cả overlap? → Trả 1.

Hướng tiếp cận

Tương đương bài 14.3 (Non-overlapping Intervals): mỗi mũi tên ứng với 1 nhóm balloon có giao chung. Đếm nhóm = số mũi tên.

Greedy sort theo end y hệt 14.3: - Sort balloons theo end. - Giữ last_end = -∞. Với mỗi balloon [s, e]: - Nếu s > last_end → cần mũi mới; last_end = e. - Ngược lại → balloon này được nổ chung với mũi hiện tại.

Code Python 3 

from typing import List

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        points.sort(key=lambda x: x[1])
        arrows = 1
        last_end = points[0][1]
        for s, e in points[1:]:
            if s > last_end:        # không giao → cần mũi mới
                arrows += 1
                last_end = e
        return arrows

Phân tích độ phức tạp

  • Thời gian: O(n log n). Bộ nhớ: O(1).

Bình luận

  • Khác biệt nhỏ với 14.3: bài 14.3 dùng >= (chạm điểm vẫn tính overlap), bài này dùng > (chạm điểm bị nổ chung). Đề LC 452 nói rõ “chạm là nổ”.
  • Hai mặt của một bài: “min arrows” = “max non-overlapping groups” = “max independent set trên interval graph”.

Bài tự luyện liên quan

  • LC 435 - Non-overlapping Intervals (bài 14.3).
  • LC 1024 - Video Stitching.

14.6 Employee Free Time (LC 759)

Đề bài

Cho schedule[i] = danh sách interval đại diện thời gian bận của employee i. Trả về tất cả interval free chung cho tất cả employee, sắp xếp tăng dần. (Không tính khoảng trước người đầu tiên bận và sau người cuối kết thúc.)

Ví dụ 

Input:  schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3, 4]]
Giải thích:
  Hợp các bận: [1,3] (gồm [1,2] + [1,3]), [4,10] (gồm [5,6] + [4,10]).
  Free chung giữa các khoảng bận: [3, 4].

Ràng buộc

  • 1 <= len(schedule) <= 50
  • Mỗi interval [start, end]

Clarifying questions

  • Một employee free toàn bộ? → Vẫn xét intersect với mọi người.
  • Output có thể là [] nếu mọi employee bận hết toàn thời gian? → Có.

Hướng tiếp cận

Bước 1: Gộp tất cả interval bận thành 1 list không phụ thuộc employee. Bước 2: Sort theo start, merge (như bài 14.1). Bước 3: Kẽ hở giữa các merged intervals = free time.

Code Python 3 

from typing import List

class Interval:
    def __init__(self, start: int = 0, end: int = 0):
        self.start, self.end = start, end


class Solution:
    def employeeFreeTime(self, schedule: "List[List[Interval]]") -> "List[Interval]":
        all_busy: list[tuple[int, int]] = []
        for emp_sched in schedule:
            for iv in emp_sched:
                all_busy.append((iv.start, iv.end))
        all_busy.sort()

        merged: list[list[int]] = []
        for s, e in all_busy:
            if merged and s <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], e)
            else:
                merged.append([s, e])

        free = []
        for i in range(1, len(merged)):
            if merged[i - 1][1] < merged[i][0]:
                free.append(Interval(merged[i - 1][1], merged[i][0]))
        return free

Phân tích độ phức tạp

  • Thời gian: O(N log N) với N = tổng số interval.
  • Bộ nhớ: O(N).

Bình luận

  • Cách tối ưu hơn - heap min-heap k-way merge: thay vì sort tất cả, dùng heap chứa head của mỗi list (schedule[i] mỗi cái đã sort). Lấy interval bận sớm nhất, merge. Khi gặp gap → free time. O(N log K) với K = số employee.
  • Pattern interval list intersection (LC 986) là biến thể tương tự.

Bài tự luyện liên quan

  • LC 986 - Interval List Intersections.
  • LC 56 - Merge Intervals.
  • LC 218 - The Skyline Problem.

Tóm tắt chương & Quyết định

Interval convention checklist

  1. Đóng [s, e] hay nửa mở [s, e)?
    • LC mặc định đóng: [1,3] và [3,5] được coi là chạm nhau ⇒ merge.
    • Một số bài lịch (calendar) dùng nửa mở: [1,3) và [3,5) không đè.
  2. Sort theo start (Merge, Insert) hay sort theo end (Greedy, Min Arrows)?
  3. Sweep line tie-break: với event tại cùng thời điểm t:
    • Meeting room (đếm overlap): kết thúc trước, bắt đầu sau → tránh đếm dư.
    • Skyline (LC 218): start trước end nếu cùng x, nhưng cẩn thận height.

Employee Free Time - visual 

e1: |==1==|       |==3==|
e2:    |==2==|       |==4==|
sort all → merge ⇒ busy: [1∪2] [3∪4]
free = complement giữa các busy block

Recap lens (vì sao Merge & Meeting xuất hiện lại)

  • Merge Intervals: minh hoạ sort + sweep - pattern dùng tiếp ở 14.2, 14.3.
  • Meeting Rooms II: minh hoạ heap = “phòng nào trống sớm nhất” - bài tổng quát cho lên lịch.