首页 > 试题广场 >

牛牛种树

[编程题]牛牛种树

热度指数：36 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛在一条街道上准备种一批树，这个街道有n个种树的坑位，分别编号为1到n。牛牛雇佣了m个小牛进行种树，每一个小牛负责一组连续编号的树坑进行种植，小牛负责的连续编号表示为[a, b)，a表示起始编号，b表示终止编号，注意种植的编号范围是左闭右开。如果小牛在种植的过程中发现某个坑位已经有树种好了，则跳过这个坑位后继续种植。问牛牛所负责的街道最终一共能够种下几棵树？返回这个结果。

输入描述:

第一行一个整数n表示街道的坑位数量，一个整数m表示小牛的数量，用空格隔开；
后m行每行两个数字ai，bi，用逗号隔开，表示对应的小牛所负责的种树编号范围[ai,bi)。

输出描述:

输出一个整数，表示最后一共能种下几棵树。

示例1

输入

输出

算法知识视频讲解

皮亚斯特里见光钻

参考区间合并

import sys
 
line1 = sys.stdin.readline()
l1 = line1.split(' ')
# 坑位数
n = int(l1[0])
# 小牛数
m = int(l1[1])
 
data = []
for line in sys.stdin:
    a = line.split(',')
    data.append(list(map(int, a)))
data.sort(key=lambda x:x[0])
interval = [data[0]]
ans = 0
for i in range(1, m):
    if interval[-1][-1] >= data[i][0]:
        interval[-1][-1] = max(interval[-1][-1], data[i][-1])
    else:
        interval.append(data[i])
 
for item in interval:
    ans += item[-1] - item[0] + 1
print(ans)

发表于 2024-11-19 15:49:14 回复(0)