C# 合并区间与扫描线

区间类问题全看一个选择：按起点排序，还是按终点排序。合并区间要前者，调度的贪心要后者，而两种写法的代码几乎一模一样。

区间问题的难点几乎全在第一行。只要顺序排对了，算法都很短，也很直白。顺序排错了，算法照样很短、很直白，只是结果是错的。

下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果粘贴过来。

模式 66 — 合并重叠区间

把所有相互接触的区间合并成一个个整块。

按起点排序。排好之后，新区间只可能和正在构建的块重叠，绝不会碰到已经完成的块：已完成的块都开始得更早，而当前这个区间比它们开始得都晚。

(int Start, int End)[] intervals = [(8, 10), (1, 3), (15, 18), (2, 6), (9, 12)];

// Sort by START. After that, an interval can only ever overlap the one
// currently being built — never anything already finished.
var sorted = intervals.OrderBy(x => x.Start).ToArray();
Console.WriteLine($"sorted by start: {string.Join(" ", sorted.Select(x => $"[{x.Start},{x.End}]"))}\n");

List<(int Start, int End)> merged = [];
foreach (var cur in sorted)
{
    if (merged.Count > 0 && cur.Start <= merged[^1].End)
    {
        var last = merged[^1];
        int newEnd = Math.Max(last.End, cur.End);
        Console.WriteLine($"[{cur.Start},{cur.End}] starts at {cur.Start} <= {last.End}, so it touches [{last.Start},{last.End}]" +
                          $"  ->  extend end to max({last.End},{cur.End}) = {newEnd}");
        merged[^1] = (last.Start, newEnd);
    }
    else
    {
        Console.WriteLine($"[{cur.Start},{cur.End}] starts after the last one ended  ->  start a new block");
        merged.Add(cur);
    }
}

Console.WriteLine($"\nmerged: {string.Join(" ", merged.Select(x => $"[{x.Start},{x.End}]"))}");

输出：

sorted by start: [1,3] [2,6] [8,10] [9,12] [15,18]

[1,3] starts after the last one ended  ->  start a new block
[2,6] starts at 2 <= 3, so it touches [1,3]  ->  extend end to max(3,6) = 6
[8,10] starts after the last one ended  ->  start a new block
[9,12] starts at 9 <= 10, so it touches [8,10]  ->  extend end to max(10,12) = 12
[15,18] starts after the last one ended  ->  start a new block

merged: [1,6] [8,12] [15,18]

关键的一行是 Math.Max(last.End, cur.End)，而不是 cur.End。

如果短区间完全落在长区间里，比如先 [1,10] 后 [2,3]，直接赋值 cur.End 会把块缩短成 [1,3]，3 之后的部分全丢了。只有一个区间嵌套在另一个区间里时才会暴露，而手写的小测试用例很少包含这种情况。

[1,3] 和 [3,5] 算不算重叠，由题目决定，不由你决定。cur.Start <= merged[^1].End 会把它们合并；< 则让它们分开。仔细读题。

代价： 排序 O(n log n)，之后 O(n)。

适用场景： 题目说合并、整合，或者“合并重叠的部分”。

模式 67 — 插入到有序列表

列表已经有序，而且互不重叠。再插入一个区间，然后重新合并。

很容易想到直接追加，再跑一遍模式 66。那样又要排一次序。其实没必要：你要排出来的顺序，就是现在已有的顺序。

(int Start, int End)[] intervals = [(1, 3), (6, 9), (12, 16)];
(int Start, int End) insert = (4, 10);

// The list is already sorted and non-overlapping, so no sort is needed at all.
// Three phases: everything strictly before, everything that touches, everything after.
List<(int Start, int End)> result = [];
int i = 0, n = intervals.Length;

while (i < n && intervals[i].End < insert.Start)
{
    Console.WriteLine($"[{intervals[i].Start},{intervals[i].End}] ends before {insert.Start} — copy it across");
    result.Add(intervals[i++]);
}

var merged = insert;
while (i < n && intervals[i].Start <= merged.End)
{
    Console.WriteLine($"[{intervals[i].Start},{intervals[i].End}] overlaps — absorb it");
    merged = (Math.Min(merged.Start, intervals[i].Start), Math.Max(merged.End, intervals[i].End));
    i++;
}
Console.WriteLine($"the absorbed block is [{merged.Start},{merged.End}]");
result.Add(merged);

while (i < n)
{
    Console.WriteLine($"[{intervals[i].Start},{intervals[i].End}] starts after — copy it across");
    result.Add(intervals[i++]);
}

Console.WriteLine($"\nresult: {string.Join(" ", result.Select(x => $"[{x.Start},{x.End}]"))}");
Console.WriteLine($"\nO(n), no sorting — the input order was already the answer's order.");

输出：

[1,3] ends before 4 — copy it across
[6,9] overlaps — absorb it
the absorbed block is [4,10]
[12,16] starts after — copy it across

result: [1,3] [4,10] [12,16]

O(n), no sorting — the input order was already the answer's order.

三个顺序执行的阶段，不用排序：新区间开始之前就结束的，照抄过去；和它接触的，全部吸收；剩下的，照抄过去。

吸收的条件是 intervals[i].Start <= merged.End，而 merged.End 会随着吸收不断变大。所以一次插入可以连续吞掉好几个区间，上面的例子正是这样。

代价： O(n)，一遍扫描。

适用场景： 往一组已经按顺序维护的区间里插入或删除。

模式 68 — 按终点排序，而不是按起点

删除最少的区间，使剩下的区间互不重叠。

这和保留最多的互不重叠区间是同一个问题，而这里排序的键反过来了。

(int Start, int End)[] intervals = [(1, 100), (2, 3), (4, 5), (6, 7)];

// Keep as many non-overlapping intervals as possible; the rest are removals.
static int Keep((int Start, int End)[] xs, bool byEnd, bool trace)
{
    var order = byEnd ? xs.OrderBy(x => x.End).ToArray() : xs.OrderBy(x => x.Start).ToArray();
    if (trace) Console.WriteLine($"  order: {string.Join(" ", order.Select(x => $"[{x.Start},{x.End}]"))}");

    int kept = 0, lastEnd = int.MinValue;
    foreach (var x in order)
    {
        if (x.Start >= lastEnd)
        {
            kept++; lastEnd = x.End;
            if (trace) Console.WriteLine($"    take [{x.Start},{x.End}]   next must start at or after {lastEnd}");
        }
        else if (trace) Console.WriteLine($"    skip [{x.Start},{x.End}]   it starts before {lastEnd}");
    }
    return kept;
}

Console.WriteLine("sorted by START:");
int a = Keep(intervals, false, true);
Console.WriteLine($"  kept {a}, removed {intervals.Length - a}\n");

Console.WriteLine("sorted by END:");
int b = Keep(intervals, true, true);
Console.WriteLine($"  kept {b}, removed {intervals.Length - b}");

Console.WriteLine($"\nSorting by start takes [1,100] first because it begins earliest,");
Console.WriteLine($"and that one interval blocks everything else. Sorting by end takes");
Console.WriteLine($"whatever finishes soonest, which leaves the most room for what follows.");

输出：

sorted by START:
  order: [1,100] [2,3] [4,5] [6,7]
    take [1,100]   next must start at or after 100
    skip [2,3]   it starts before 100
    skip [4,5]   it starts before 100
    skip [6,7]   it starts before 100
  kept 1, removed 3

sorted by END:
  order: [2,3] [4,5] [6,7] [1,100]
    take [2,3]   next must start at or after 3
    take [4,5]   next must start at or after 5
    take [6,7]   next must start at or after 7
    skip [1,100]   it starts before 7
  kept 3, removed 1

Sorting by start takes [1,100] first because it begins earliest,
and that one interval blocks everything else. Sorting by end takes
whatever finishes soonest, which leaves the most room for what follows.

按起点排序时，[1,100] 开始得最早，所以最先被选中，而这一个区间挡住了其他所有区间。保留一个，删除三个。

按终点排序时，选的是最先结束的区间，给后面留下的空间最多。保留三个，删除一个。

贪心要选最早结束的，因为一个区间开始得多早，说明不了它身后还留下多少空间。

这就是经典的活动选择问题的论证，也是这一类问题值得当成两个模式、而不是一个模式来讲的原因。合并要按起点排序，调度要按终点排序。两个循环看起来几乎一样，所以排序键选错了，得到的答案看着合理，也不会报任何错。

代价： O(n log n)。

适用场景： 目标是尽量多安排、或者尽量少删除，比如会议安排、无重叠区间、“最多可以参加的会议数目”。

模式 69 — 扫描线

至少需要几间会议室，才能让所有会议互不冲突？

别再想区间了。每场会议是时间轴上的两个事件：开始时需要一间会议室，结束时腾出一间。把所有事件按时间排序，维护一个动态计数。峰值就是答案。

(int Start, int End)[] meetings = [(0, 30), (5, 10), (15, 20), (6, 8)];

// Stop thinking about intervals. Think about EVENTS on a timeline: a start
// adds a room, an end frees one. The peak is the answer.
var events = meetings
    .SelectMany(m => new[] { (Time: m.Start, Delta: +1), (Time: m.End, Delta: -1) })
    .OrderBy(e => e.Time).ThenBy(e => e.Delta)      // an end at time t before a start at t
    .ToArray();

int inUse = 0, peak = 0;
foreach (var e in events)
{
    inUse += e.Delta;
    peak = Math.Max(peak, inUse);
    Console.WriteLine($"t={e.Time,2}  {(e.Delta > 0 ? "start" : "end  ")}  rooms in use: {inUse}   peak {peak}");
}

Console.WriteLine($"\nrooms needed: {peak}");
Console.WriteLine();
Console.WriteLine("ThenBy(Delta) matters: at a shared time an END (-1) must be processed");
Console.WriteLine("before a START (+1), or a room that is being freed gets counted twice.");
Console.WriteLine("That is the difference between a meeting ending at 10 and one starting");
Console.WriteLine("at 10 needing one room or two.");

输出：

t= 0  start  rooms in use: 1   peak 1
t= 5  start  rooms in use: 2   peak 2
t= 6  start  rooms in use: 3   peak 3
t= 8  end    rooms in use: 2   peak 3
t=10  end    rooms in use: 1   peak 3
t=15  start  rooms in use: 2   peak 3
t=20  end    rooms in use: 1   peak 3
t=30  end    rooms in use: 0   peak 3

rooms needed: 3

ThenBy(Delta) matters: at a shared time an END (-1) must be processed
before a START (+1), or a room that is being freed gets counted twice.
That is the difference between a meeting ending at 10 and one starting
at 10 needing one room or two.

正确性全靠 .ThenBy(e => e.Delta)，而它很容易被漏掉。在同一时刻，结束（-1）必须先于开始（+1）处理。一场会议 10 点结束、另一场 10 点开始，两场一共只需要一间会议室，不是两间。顺序反过来，计数就会瞬间冲高，而峰值（也就是答案）恰恰会被这种瞬间冲高搞错。

这就是第 3 篇的差分数组，只不过从数组搬到了时间轴上，而且坐标没有压缩。如果时间值很大又很稀疏，下一步就是模式 29。

代价： 排序 O(n log n)，扫描 O(n)。

适用场景： 问的是并发：同一时刻有多少个、最忙的时刻、最少需要多少资源。不是总共有多少对重叠，而是同时有多少个重叠。

模式 70 — 求两个区间列表的交集

两个列表都已经有序，各自内部互不重叠。找出两者都覆盖的每一段。

这就是第 1 篇的双指针遍历，只是比较方式不同。

(int Start, int End)[] a = [(0, 2), (5, 10), (13, 23), (24, 25)];
(int Start, int End)[] b = [(1, 5), (8, 12), (15, 24), (25, 26)];

// Both lists are already sorted, so this is the two-pointer walk from part 1.
List<(int, int)> result = [];
int i = 0, j = 0;

while (i < a.Length && j < b.Length)
{
    int lo = Math.Max(a[i].Start, b[j].Start);      // the later of the two starts
    int hi = Math.Min(a[i].End, b[j].End);          // the earlier of the two ends

    if (lo <= hi)
    {
        result.Add((lo, hi));
        Console.WriteLine($"a[{i}]=[{a[i].Start},{a[i].End}]  b[{j}]=[{b[j].Start},{b[j].End}]  ->  overlap [{lo},{hi}]");
    }
    else
    {
        Console.WriteLine($"a[{i}]=[{a[i].Start},{a[i].End}]  b[{j}]=[{b[j].Start},{b[j].End}]  ->  no overlap");
    }

    // Advance whichever ends first — it can never overlap anything later.
    if (a[i].End < b[j].End) i++; else j++;
}

Console.WriteLine($"\nintersections: {string.Join(" ", result.Select(x => $"[{x.Item1},{x.Item2}]"))}");
Console.WriteLine();
Console.WriteLine("The overlap of two intervals is always [max(starts), min(ends)],");
Console.WriteLine("and it is empty exactly when that comes out backwards.");

输出：

a[0]=[0,2]  b[0]=[1,5]  ->  overlap [1,2]
a[1]=[5,10]  b[0]=[1,5]  ->  overlap [5,5]
a[1]=[5,10]  b[1]=[8,12]  ->  overlap [8,10]
a[2]=[13,23]  b[1]=[8,12]  ->  no overlap
a[2]=[13,23]  b[2]=[15,24]  ->  overlap [15,23]
a[3]=[24,25]  b[2]=[15,24]  ->  overlap [24,24]
a[3]=[24,25]  b[3]=[25,26]  ->  overlap [25,25]

intersections: [1,2] [5,5] [8,10] [15,23] [24,24] [25,25]

The overlap of two intervals is always [max(starts), min(ends)],
and it is empty exactly when that comes out backwards.

所有工作都靠两个事实。

两个区间的重叠部分永远是 [max(starts), min(ends)]，而且恰好在它颠倒时为空，即 lo > hi。一个表达式同时处理重叠和不重叠两种情况，不用另外判断是否相交。

另一个事实是：谁先结束，就推进谁。它不可能和另一个列表里后面的区间重叠，因为后面的区间都在它结束之后才开始。这和模式 1 里丢弃元素的论证相同，也是这次遍历是线性而不是平方级的原因。

代价： O(n + m)。

适用场景： 比较两份日程，比如共同的空闲时间、双方都有空的时段、有重叠的预订。

要点

• 合并按起点排序，调度的贪心按终点排序。 代码不会告诉你选了哪一个，两种选法的输出看起来都合理。
• 扩展时用 max(lastEnd, current.End)。 直接赋值 current.End 只在一个区间嵌套在另一个区间里时出错。
• 端点相接算不算重叠，由题目决定。 <= 会把 [1,3] 和 [3,5] 合并，< 不会。
• 已经有序的列表不用再排序。 插入就是三个顺序执行的阶段，O(n)。
• 贪心要选最早结束的。 开始得多早，说明不了身后留下多少空间。
• 扫描线把区间变成 +1 和 −1 事件。 时间相同时先处理结束再处理开始，否则峰值会错。
• 重叠部分是 [max(starts), min(ends)]，颠倒时为空。 一个表达式，不需要单独的相交判断。

第 15 篇讲回溯：一个模板，五道题。人人都会漏掉的那一行，是撤销上一步的那一行。