リリース・改善中
貪欲法 ガイド · 3/6
この章は現在、英語でのみ提供しています。
This chapter implements two classic greedy algorithms in Python, interval scheduling and Huffman code lengths, then ports interval scheduling to C++, Java and TypeScript.
import heapq
def max_non_overlapping(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
"""Most pairwise-disjoint half-open intervals [start, end)."""
chosen: list[tuple[int, int]] = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]):
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
def huffman_code_lengths(freq: dict[str, int]) -> dict[str, int]:
"""Return the bit length of each symbol's Huffman code."""
symbols = list(freq)
if len(symbols) <= 1:
return {s: 1 for s in symbols}
heap = [(w, i) for i, w in enumerate(freq.values())]
heapq.heapify(heap)
parent = [-1] * len(symbols) # node id -> parent id; ids >= n are internal
while len(heap) > 1:
w1, a = heapq.heappop(heap)
w2, b = heapq.heappop(heap)
node = len(parent)
parent.append(-1)
parent[a] = parent[b] = node
heapq.heappush(heap, (w1 + w2, node))
depth = [0] * len(parent)
for node in range(len(parent) - 2, -1, -1):
depth[node] = depth[parent[node]] + 1
return {s: depth[i] for i, s in enumerate(symbols)}sorted(..., key=lambda iv: iv[1]) returns a new list ordered by end time; the input is untouched.last_end starts at minus infinity, so the first interval is always accepted.start >= last_end: a half-open interval may start exactly when the previous one ends. Use > for closed intervals.last_end only, never with earlier choices.(weight, node id); ids break ties deterministically and never raise TypeError.from collections import Counter
meetings = [(1, 3), (2, 5), (4, 7), (1, 8), (6, 9), (8, 10)]
print(max_non_overlapping(meetings)) # [(1, 3), (4, 7), (8, 10)]
lengths = huffman_code_lengths({"a": 5, "b": 9, "c": 12, "d": 13, "e": 16, "f": 45})
print(lengths) # {'a': 4, 'b': 4, 'c': 3, 'd': 3, 'e': 3, 'f': 1}
text = "abracadabra"
counts = Counter(text)
bits = sum(counts[s] * n for s, n in huffman_code_lengths(counts).items())
print(bits, "bits vs", 8 * len(text), "at 8 bits each") # 23 bits vs 88 at 8 bits each#include <algorithm>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
using Interval = std::pair<long long, long long>; // [start, end)
std::vector<Interval> maxNonOverlapping(std::vector<Interval> intervals) {
std::sort(intervals.begin(), intervals.end(),
[](const Interval& a, const Interval& b) { return a.second < b.second; });
std::vector<Interval> chosen;
long long lastEnd = std::numeric_limits<long long>::min();
for (const auto& [start, end] : intervals) {
if (start >= lastEnd) {
chosen.push_back({start, end});
lastEnd = end;
}
}
return chosen;
}
int main() {
std::vector<Interval> meetings{{1, 3}, {2, 5}, {4, 7}, {1, 8}, {6, 9}, {8, 10}};
for (const auto& [s, e] : maxNonOverlapping(meetings)) std::cout << s << ' ' << e << '\n';
}Taking the vector by value sorts a copy. Structured bindings need C++17.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class IntervalScheduling {
record Interval(long start, long end) {}
static List<Interval> maxNonOverlapping(Interval[] intervals) {
Interval[] sorted = intervals.clone();
Arrays.sort(sorted, Comparator.comparingLong(Interval::end));
List<Interval> chosen = new ArrayList<>();
long lastEnd = Long.MIN_VALUE;
for (Interval iv : sorted) {
if (iv.start() >= lastEnd) {
chosen.add(iv);
lastEnd = iv.end();
}
}
return chosen;
}
public static void main(String[] args) {
Interval[] meetings = {
new Interval(1, 3), new Interval(2, 5), new Interval(4, 7),
new Interval(1, 8), new Interval(6, 9), new Interval(8, 10),
};
System.out.println(maxNonOverlapping(meetings));
}
}Records need Java 16+. Comparator.comparingLong avoids subtraction overflow.
type Interval = readonly [start: number, end: number];
export function maxNonOverlapping(intervals: readonly Interval[]): Interval[] {
const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
const chosen: Interval[] = [];
let lastEnd = -Infinity;
for (const [start, end] of sorted) {
if (start >= lastEnd) {
chosen.push([start, end]);
lastEnd = end;
}
}
return chosen;
}
console.log(maxNonOverlapping([[1, 3], [2, 5], [4, 7], [1, 8], [6, 9], [8, 10]]));sort works in place, so the spread copy protects the input. Within the safe integer range, a[1] - b[1] is a fine comparator.
>=) and sorting a copy.
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。