最小区间

[编程题]最小区间

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

给定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

输出描述:

两个数，分别为最小区间的左右边界

示例1

输入

输出

2 4

算法知识视频讲解

Python

知易行难20180822101322

通过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]))

发表于 2018-08-29 10:50:46 回复(0)