给定k个有序数组, 每个数组有个N个元素,找出一个最小的闭区间,使其包含每个数组中的至少一个元素。
给定两个区间[a,b], [c,d]:
如果 b-a < d-c,则认为[a, b]是更小的区间;
如果 b-a == d-c,且a < c,则认为[a, b]是更小的区间。
K
N
x11 x12 x13 ... x1n
...
xk1 xk2 xk3 ... xkn
两个数,分别为最小区间的左右边界
3 3 2 12 14 2 6 9 4 7 19
2 4
通过50%,提示超时
K = int(input())
N = int(input())
data = []
data1 = []
for i in range(K):
g = input().split(" ")
d = [int (j) for j in g]
data.append(d)
for i in data:
for j in i:
data1.append(j)
data1 = set(data1)
data1 = list(data1)
data1.sort()
start = 0
end = 0
edge = len(data1)
s = 0
e = 0
M = []
def findMin():
m = data[0][0]
for i in data:
mi = min(i)
if mi<m:
m = mi
return m
def getD(j,s,e):
if s<=j<=e:
return 1
else:
return 0
def isMin(s,e):
num = 0;
for i in data:
for j in i:
r = getD(j,s,e)
if r == 1:
break
if r == 0:
return 0
return 1
def getMin(data):
m= data[0]
i = 1
l = len(data)
while i < l:
if (m[1] - m[0]) == (data[i][1] - data[i][0]) and m[0] < data[i][0]:
i+=1
continue
elif (m[1] - m[0]) < (data[i][1] - data[i][0]):
i+=1
continue
else:
m = data[i]
i+=1
return m
start = end = data1.index(findMin())
while end+1 != edge:
s = data1[start]
e = data1[end]
r = isMin(s,e)
if r == 1:
M.append([s,e])
start +=1
else:
end += 1
start += 1
while start <= end:
s = data1[start]
e = data1[end]
r = isMin(s,e)
if r == 1:
M.append([s,e])
start +=1
else:
break
re = getMin(M)
print("{0} {1}".format(re[0],re[1]))