区間スケジューリングとマージ
終了時刻でソートしてmeeting-roomsとnon-overlapping-intervalsを解き、開始時刻でソートしてmerge-intervalsを解きます。
「区間スケジューリングとマージ」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
区間問題の概要
区間問題は、スケジューリング、カレンダー管理、リソース割り当ての面接で頻繁に登場します。重要なパターンは、重複する区間をマージする、必要な会議室の最小数を数える、重ならない区間の最大集合を見つける、新しい区間を挿入することです。多くの区間問題は、同じ手順から始まります。つまり、区間を開始時刻でソートすることです（問題によっては終了時刻でソートします）。正しいソートキーを選ぶことが、最も難しい部分になる場合がよくあります。
# Intervals: each = [start, end] (inclusive or exclusive by problem)
# Example:
intervals = [[1,3],[2,6],[8,10],[15,18]]
# Sorted by start (already sorted here)
# Visually:
# [1,3] |-|
# [2,6] |---|
# [8,10] |--|
# [15,18] |---|
print('Intervals ready for analysis')重複する区間のマージ
Merge Intervals（LeetCode 56）は、区間のリストを受け取り、重複する区間をすべてマージする問題です。アルゴリズムは、まず開始時刻でソートします。ソート済みのリストを順に調べ、現在の区間が最後にマージした区間と重なる場合（現在の開始時刻 ≤ 最後にマージした区間の終了時刻）、両方の終了時刻の最大値を最後にマージした区間の終了時刻に設定して延長します。重ならない場合は、現在の区間を新しいマージ済み区間として追加します。計算量は、ソートに O(n log n)、マージに O(n) かかります。
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
# Overlapping: extend the last interval
merged[-1][1] = max(last_end, end)
else:
# Non-overlapping: add as new interval
merged.append([start, end])
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))
# [[1,5]] (touching intervals merge)区間の挿入
Insert Interval（LeetCode 57）は、ソート済みで互いに重ならない区間のリストに新しい区間を挿入し、再度マージする問題です。次の3段階で処理します。(1) 新しい区間の開始時刻より前に終了する区間をすべて追加します。(2) 新しい区間と重なる区間をすべてマージし、その境界を広げます。(3) 残りの区間をすべて追加します。この問題ではすでにソート済みなので、O(n log n)のソート後にO(n)の1回の走査だけで処理できます。
def insert_interval(intervals, new_interval):
result = []
i = 0
n = len(intervals)
# Phase 1: intervals before new_interval
while i < n and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge overlapping intervals
while i < n and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
result.append(new_interval)
# Phase 3: remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
print(insert_interval([[1,3],[6,9]], [2,5])) # [[1,5],[6,9]]
print(insert_interval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
# [[1,2],[3,10],[12,16]]会議室 I：すべてに参加できるか
Meeting Rooms I（LeetCode 252）は、会議の時間区間を受け取り、1人がすべての会議に参加できるかどうかを判定する問題です。開始時刻でソートし、いずれかの会議が前の会議の終了時刻より前に始まる場合は重なっています。これは最も基本的な区間チェックで、全体の計算量は O(n log n) です。重要なポイントは、ソート後は隣接する区間のペアだけを比較すればよいことです。
def can_attend_meetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
# Current meeting starts before previous ends?
if intervals[i][0] < intervals[i-1][1]:
return False
return True
print(can_attend_meetings([[0,30],[5,10],[15,20]])) # False (0,30 overlaps 5,10)
print(can_attend_meetings([[7,10],[2,4]])) # True (4 < 7, no overlap)会議室 II：必要な部屋の最小数
Meeting Rooms II（LeetCode 253）は、すべての会議を同時に開催するために必要な会議室の最小数を求める問題です。最も早く終了する部屋を追跡するために最小ヒープを使います。会議を開始時刻でソートします。新しい会議ごとに、最も早く終了する部屋の終了時刻より後に始まる場合は、その部屋を再利用します（popしてpushします）。そうでなければ、新しい部屋を開きます。最後のヒープサイズが必要な部屋数になります。
import heapq
def min_meeting_rooms(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[0]) # sort by start
heap = [] # min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse earliest-ending room
else:
heapq.heappush(heap, end) # open a new room
return len(heap)
print(min_meeting_rooms([[0,30],[5,10],[15,20]])) # 2
print(min_meeting_rooms([[7,10],[2,4]])) # 1
print(min_meeting_rooms([[9,10],[4,9],[4,17]])) # 2部屋数を数える別解：スイープライン
別の O(n log n) のアプローチとして、スイープラインがあります。各区間について、開始イベント（+1）と終了イベント（-1）を作成します。すべてのイベントを時刻でソートします（同時刻の場合、区間の終端を始端より先に処理すると、終端を含めない扱いにできます）。左から右へ走査し、開催中の会議数を累計します。最大の累計値が必要な部屋数の最小値です。この方法は直感的に理解しやすく、区間に関する他のカウント問題にも一般化できます。
def min_rooms_sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # meeting starts
events.append((end, -1)) # meeting ends
# Sort: same time → end (-1) before start (1) if exclusive
events.sort(key=lambda x: (x[0], x[1]))
max_rooms = current = 0
for _, delta in events:
current += delta
max_rooms = max(max_rooms, current)
return max_rooms
print(min_rooms_sweep([[0,30],[5,10],[15,20]])) # 2
print(min_rooms_sweep([[1,5],[2,6],[3,7]])) # 3 (all overlap at t=3)重ならない区間：最大選択数
Non-Overlapping Intervals（LeetCode 435）は、残りの区間が重ならないようにするために削除する区間の最小数を求める問題です。これは、重ならない区間の最大数（アクティビティ選択）を求め、その残りを削除数として返すことと同じです。終了時刻でソートし、終了が最も早い区間を貪欲に残します（後続の区間のための余地を最大化できます）。次の区間が重なる場合は、その区間を破棄して削除数を増やします。
def erase_overlap_intervals(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[1]) # sort by END time
removals = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
last_end = end # keep this interval
else:
removals += 1 # remove this interval (it overlaps)
return removals
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])) # 1 (remove [1,3])
print(erase_overlap_intervals([[1,2],[1,2],[1,2]])) # 2
print(erase_overlap_intervals([[1,2],[2,3]])) # 0 (no overlap)なぜ開始時刻ではなく終了時刻でソートするのか
活動選択（最大非重複集合）では、終了時刻でソートする方法が最適であることが証明されています。直感的には、早く終了する活動ほど、後続の活動のために多くの余地を残せるからです。開始時刻でソートすると、開始は早いものの非常に長い活動を選んでしまい、後から選べる短い活動を多数妨げる可能性があります。交換論法では、最適解が最も早く終了する G ではなく活動 A を選んでいるとします。このとき A を G に置き換えます。G の終了時刻は A より遅くないため、A が競合しなかった活動と競合することもありません。
# Counterexample for sorting by START time:
# [[1,10],[2,3],[4,5]] — sorted by start: [1,10],[2,3],[4,5]
# Sort-by-start greedy keeps [1,10], can't add [2,3] or [4,5] (all overlap [1,10])
# Selects: 1 interval
# Sort-by-end greedy:
# [[2,3],[4,5],[1,10]] — sorted by end
# Keep [2,3] (end=3), then [4,5] (start=4 >= 3, keep), then [1,10] (start=1 < 5, skip)
# Selects: 2 intervals — OPTIMAL
intervals = [[1,10],[2,3],[4,5]]
intervals.sort(key=lambda x: x[1])
last_end = float('-inf')
count = 0
for s, e in intervals:
if s >= last_end:
count += 1; last_end = e
print('Max non-overlapping:', count) # 2区間リストの交差
Interval List Intersections（LeetCode 986）は、2つのソート済み区間リストから、交差するすべてのペアを求める問題です。2ポインタ approach を使用します。各ステップで、現在のペアの交差部分（開始時刻の最大値と終了時刻の最小値）を計算します。開始時刻 ≤ 終了時刻であれば、その交差部分は有効です。次に、終了時刻が早い方の区間のポインタを進めます。計算量は O(m+n) です。
def interval_intersection(A, B):
result = []
i = j = 0
while i < len(A) and j < len(B):
# Intersection boundaries
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
result.append([lo, hi]) # valid intersection
# Advance pointer of interval that ends first
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(interval_intersection(A, B))
# [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]Partition Labels
Partition Labels（LeetCode 763）は、各文字が高々1つの部分にしか現れないように、文字列をできるだけ多くの部分に分割する問題です。貪欲法では、各文字について最後に現れる位置を求めます。文字列を走査しながら max_end を保持します。i == max_end になったら現在の部分が完成したので、その長さを記録し、新しい部分を開始します。これは、見方を変えると区間マージ問題です。
def partition_labels(s):
last = {c: i for i, c in enumerate(s)} # last occurrence of each char
partitions = []
start = max_end = 0
for i, c in enumerate(s):
max_end = max(max_end, last[c])
if i == max_end: # partition complete
partitions.append(max_end - start + 1)
start = i + 1
return partitions
print(partition_labels('ababcbacadefegdehijhklij'))
# [9, 7, 8] — parts 'ababcbaca', 'defegde', 'hijhklij'区間問題のまとめ
区間について、次の4つのパターンを身につけてください。(1) マージ：開始時刻でソートし、重なっていれば最後の区間を拡張します。(2) 部屋数のカウント：開始時刻でソートし、終了時刻の最小ヒープを使用します。(3) 最大非重複集合：終了時刻でソートし、貪欲に選択します。(4) 挿入：3段階の線形走査を行います。ソートの基準が重要です。マージでは開始時刻、最大選択では終了時刻を使用します。計算量は常にソートが支配的な O(n log n) で、マージや走査は O(n) です。
# Quick reference:
# Merge intervals: sort by start, extend if overlap
# Insert interval: three-phase linear scan
# Meeting rooms (can?): sort by start, check consecutive overlap
# Meeting rooms (min?): sort by start, min-heap of end times / sweep
# Max non-overlapping: sort by END, greedy keep
# Min removals: n - max_non_overlapping
# Interval intersection: two pointers on sorted lists
print('Pattern: sort key is the decisive choice')
print('Merge → sort by start')
print('Activity selection → sort by end')
print('Room count → sort by start + heap of ends')理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、開始時刻でソートし、重なりが発生したら最後の区間を拡張して区間をマージする方法、最小会議室数を、開始時刻でのソートと終了時刻の最小ヒープによって求め、最も早く終了する部屋が空いたら再利用する方法、そして終了時刻による貪欲な選択で最大非重複区間を求める方法を学びました。次は Jump Game I と II に取り組みます。貪欲な範囲拡張によって、到達可能性と最小ジャンプ数を求める問題です。
よくある質問
「区間スケジューリングとマージ」レッスンは無料ですか？
はい。「区間スケジューリングとマージ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「区間スケジューリングとマージ」で何を学びますか？
終了時刻でソートしてmeeting-roomsとnon-overlapping-intervalsを解き、開始時刻でソートしてmerge-intervalsを解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「区間スケジューリングとマージ」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 貪欲法とDP：使い分け
- 区間スケジューリングとマージ
- Jump Game IとII
- Task SchedulerとGas Station