【华为OD机试2023】区间连接器Python

题目描述：

有一组区间 [a0, b0], [a1, b1], ... (a, b 表示起点, 终点)，区间有可能重叠、相邻，重叠或相邻则可以合并为更大的区间；给定一组连接器[x1, x2, x3, ...]（x 表示连接器的最大可连接长度，即 x>=gap），可用于将分离的区间连接起来，但两个分离区间之间只能使用1个连接器；请编程实现使用连接器后，最少的区间数结果。

区间数量 <10000；a,b 均 <=10000

连接器梳理 <10000; x <=10000

输入描述：

区间组：[1,10],[15,20],[18,30],[33,40]

连接器组：[5,4,3,2]

输出描述：

1

说明：合并后：[1,10], [15,30], [33,40]，使用 5, 3 两个连接器连接后只剩下 [1,40]

示例1

输入：

[1,10],[15,20],[18,30],[33,40]

[5,4,3,2]

输出：

1

说明：

合并后：[1,10], [15,30], [33,40]，使用 5, 3 两个连接器连接后只剩下 [1,40]

示例2

输入：

[1,2],[3,5],[7,10],[15,20],[30,100]

[5,4,3,2,1]

输出：

2

说明：

无重叠和相邻，使用 1，2， 5 三个连接器连接后只剩下 [1, 20], [30, 100]

解题思路：

先把区间按照左端点升序、右端点升序排列好，然后依次遍历，把组合好的区间存储在combined列表中——如果combined[-1]的右端点小于等于当前遍历区间的左端点，那么修改combined[-1]的右端点值（取这两个区间右端点大的那个的值）；否则，把该区间压入combined

得到连接好的区间后，计算出相邻区间之间的距离，存储在dis列表中，把dis按照数字大小升序排列；再把连接器的数据按照数字大小升序排列

两层for循环，如果连接器的长度大于等于区间距离，那么弹出lianjieqi[0]，表示已经使用该连接器，并且combined列表长度减一，搞定

lst=list(eval(input()))
lianjieqi=sorted(eval(input()))
lst=sorted(lst,key=lambda x:(x[0],x[1]))
combined=[]

for i,value in enumerate(lst):
    if i==0:
        combined.append(value)
    else:
        if value[0]<=combined[-1][1]:
            combined[-1][1]=max(combined[-1][1],value[1])
        else:
            combined.append(value)

dis=[]
for i in range(len(combined)):
    if i == len(combined)-1:
        break
    else:
        dis.append(combined[i+1][0]-combined[i][1])
count=len(combined)
dis=sorted(dis)
for i in lianjieqi:
    for j in dis:
        if i>=j:
            dis.pop(0)
            count-=1
print(count)