максимизация интервального планирования - PullRequest
Новая
       47

максимизация интервального планирования

0 голосов
/ 02 марта 2020

Я строю эту программу в Python 3. Мне нужно, чтобы она работала быстрее. в основном это жадный алгоритм.

Роль заключается в том, что действия не могут сосуществовать, если одно заканчивается в 4, а другое начинается в 4, они не могут находиться в одной комнате. на выходе должны быть самые возможные виды деятельности 

import sys

[n, k] = sys.stdin.readline().split()
n = int(n)
k = int(k)

if int(n) < 2:
    print(n)
    exit()

sortedKittens = []
x = sys.stdin.read().split()

for i in range(n):
    sortedKittens.append((int(x[i*2]), int(x[i*2+1])))

sortedKittens.sort(key=lambda a: a[1])

# count Kittens
totalKittens = 0

beds = [0 for i in range(k)]
for [s, f] in sortedKittens:
    for index, last_f in enumerate(beds):
        if s > last_f:
            totalKittens += 1
            beds.pop(index)
            beds.insert(0, f)
            break

print(totalKittens)
...