python - 如何将 O(N*M) 优化为 O(n**2)？

Question

我正在尝试解决 USACO 的挤奶奶牛问题。问题陈述在这里：https ://train.usaco.org/usacoprob2?S=milk2&a=n3lMlotUxJ1

给定一系列二维数组形式的间隔，我必须找到最长的间隔和没有发生挤奶的最长间隔。

前任。给定数组[[500,1200],[200,900],[100,1200]]，最长的间隔将是 1100，因为有连续挤奶，而没有挤奶的最长间隔将是 0，因为没有休息时间。

我试过看看使用字典是否会减少运行时间，但我没有取得太大的成功。

f = open('milk2.in', 'r')
w = open('milk2.out', 'w')

#getting the input
farmers = int(f.readline().strip())
schedule = []
for i in range(farmers):
    schedule.append(f.readline().strip().split())


#schedule = data
minvalue = 0
maxvalue = 0

#getting the minimums and maximums of the data 
for time in range(farmers):
    schedule[time][0] = int(schedule[time][0])
    schedule[time][1] = int(schedule[time][1])
    if (minvalue == 0):
        minvalue = schedule[time][0]
    if (maxvalue == 0):
        maxvalue = schedule[time][1]
    minvalue = min(schedule[time][0], minvalue)
    maxvalue = max(schedule[time][1], maxvalue)

filled_thistime = 0
filled_max = 0

empty_max = 0
empty_thistime = 0

#goes through all the possible items in between the minimum and the maximum
for point in range(minvalue, maxvalue):
    isfilled = False
    #goes through all the data for each point value in order to find the best values
    for check in range(farmers):
        if point >= schedule[check][0] and point < schedule[check][1]:
            filled_thistime += 1
            empty_thistime = 0
            isfilled = True
            break
    if isfilled == False:
        filled_thistime = 0
        empty_thistime += 1
    if (filled_max < filled_thistime) : 
        filled_max = filled_thistime 
    if (empty_max < empty_thistime) : 
        empty_max = empty_thistime 
print(filled_max)
print(empty_max)
if (filled_max < filled_thistime):
    filled_max = filled_thistime

w.write(str(filled_max) + " " + str(empty_max) + "\n")
f.close()
w.close()

该程序运行良好，但我需要减少运行时间。

标签： pythonpython-3.xalgorithmoptimizationdata-structures

Answer 1

如评论中所述，如果输入已排序，则复杂度可能为 O(n)，如果不是这种情况，我们需要先对其进行排序，复杂度为 O(nlog n)：

lst = [ [300,1000],
[700,1200],
[1500,2100] ]

from itertools import groupby

longest_milking = 0
longest_idle = 0

l = sorted(lst, key=lambda k: k[0])

for v, g in groupby(zip(l[::1], l[1::1]), lambda k: k[1][0] <= k[0][1]):
    l = [*g][0]
    if v:
        mn, mx = min(i[0] for i in l), max(i[1] for i in l)
        if mx-mn > longest_milking:
            longest_milking = mx-mn
    else:
        mx = max((i2[0] - i1[1] for i1, i2 in zip(l[::1], l[1::1])))
        if mx > longest_idle:
            longest_idle = mx

# corner case, N=1 (only one interval)
if len(lst) == 1:
    longest_milking = lst[0][1] - lst[0][0]

print(longest_milking)
print(longest_idle)

印刷：

900
300

对于输入：

lst = [ [500,1200],
        [200,900],
        [100,1200] ]

印刷：

1100
0