Kattis: "watering Grass" Interval covering problem, why is my code so slow?

Question

В настоящее время я практикуюсь, выполняя эту задачу на Python: https://open.kattis.com/problems/grass

Он работает так, как должен, вывод хорош, но продолжает работать слишком медленно. Я пробовал перемещать некоторые вещи, но ничего не работает. Я добавил довольно много кода, но я пытаюсь следовать принципу наименее функциональных фрагментов кода, чтобы кто-то мог запустить это сам.

Я использую некоторый синтаксический анализ, чтобы рассматривать круги как подинтервалы (голова, хвост) в большом интервале, который должен быть покрыт.

# Getmax is used in the algorithm to find the largest tail of all subintervals
def getmax(liste, t):
    big = -1
    start = None
    indexOfNewT = 0
    for n in range(len(liste)):
        if liste[n][0] <= t:

            if liste[n][1] >= big:
                big = liste[n][1]
                start = liste[n][0]
                indexOfNewT = n
    # In order to get a smaller list that i need to find a large tail in, I remove the elements that I add
    del liste[indexOfNewT]
    res = (start, big)
    if start == None:
        return None, None, None
    return big, res, liste


 # Here is the actual algorithm that solves the issue. 'Intervals' is a list of sublists which all
 #contain n numbers of intervals [start,end]. Lowerbound, upperBound are numbers indicating length of 
 #Grass field (Lowerbound is always 0)  
 #I was wondering whether the sorting could be done in a more clever way?
 def solver(lowerbound, upperBound, Intervals):
    Intervals.sort(key=lambda x: x[1])
    S = []
    t = lowerbound

    if (Intervals[len(Intervals)-1][1] < upperBound):
        return -1
    while t < upperBound:
        # getmax, her leder vi efter den største hale på et interval, mens head
        # på samme interval ikke er mere end det sidst addede element (t)
        get, i, newlist = getmax(Intervals, t)
        Intervals = newlist
        if get is None:
            return -1
        S.append(i)
        t = get
    return len(S)


    #method for converting circles to intervals with a head and a tail coordinate 
def getB(a, c):
    inter = abs(c * c - a * a)

# Here we actually parse the input, this method also calls the actual algorithm and provides output
#for every test case
def parse():
Innerintervals = []
# this is the loop that reads lines, if the line has more than three elements, it indicates a new 
# test case is coming. The reading itself happens at O(n) i dont think i could do better, could I?
for line in sys.stdin:
    current = line.split()
    if (len(current)) >= 3:
        if Innerintervals:
           # the algorithm is directly executed and printed as a test case is read
           print(solver(0, grassLen, Innerintervals))

        grassLen = float(current[1])
        width = float(current[2])
        Innerintervals = []

    else:
        linesplit = line.split()
        #Using a bit of pythagoras to get the places where the circle touches the edges of the field
        # I use this to be able to treat this a a interval covering problem
        position = int(linesplit[0])
        radius = int(linesplit[1])
        lenOfB = getB(width/2,radius)
        IntervalMin = position - lenOfB
        IntervalMax = position + lenOfB
        Innerintervals.append([IntervalMin,IntervalMax])


# as a result of my loop being constructed a bit clumsy, the last element is executed here
print(solver(0, grassLen, Innerintervals))

#running parse to starte the whole thing
parse()

Я бы очень хотел получить несколько советов, на случай, если какой-либо код "воняет" или если его можно оптимизировать где-нибудь, где я мог бы сделать некоторые очевидные промахи.