M29947: 校门外的树又来了

greedy, interval merging, stack, http://cs101.openjudge.cn/practice/29947/

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入

输入的第一行有两个整数L（1 <= L <= 10^9）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出

输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入

样例输出

来源

yan

思路：区间合并。排序是为了保证取交集的方向唯一，这种单向关系可以避免分类讨论。

python

L, M = map(int, input().split())
intervals = []

for _ in range(M):
    s, e = map(int, input().split())
    if s > e:
        s, e = e, s
    intervals.append((s, e))

# 按起点排序
intervals.sort()

# 合并区间
merged = []
for s, e in intervals:
    if not merged or s > merged[-1][1] + 1:
        merged.append([s, e])
    else:
        merged[-1][1] = max(merged[-1][1], e)

# 计算被砍掉的树总数
cut = sum(e - s + 1 for s, e in merged)
remain = (L + 1) - cut

print(remain)

“栈”模拟区间嵌套层数

python

n, m = map(int, input().split())
res = n + 1
events = []  # (坐标, 类型) 类型: 0=左端点, 1=右端点

for _ in range(m):
    l, r = map(int, input().split())
    if l > r: l, r = r, l
    events.append((l, 0))
    events.append((r, 1))

events.sort()
stack = []

for x, typ in events:
    if typ == 0:
        stack.append(x)
    else:
        left = stack.pop()
        if not stack:
            res -= x - left + 1

print(res)

M29947: 校门外的树又来了 ​

M29947: 校门外的树又来了