Python TLE for Activities

[coding_all_day]

I am trying to solve this question: https://www.spoj.com/problems/ACTIV/

I’ve written up a DP solution that I think is optimal in terms of time complexity - n * log(n)

'''
https://www.spoj.com/problems/ACTIV/
'''

from collections import defaultdict


def bin_search(classes, target):
    hi = len(classes)-1
    lo = 0
    while lo <= hi:
        mid = (hi + lo)//2
        if classes[mid][1] > target:
            hi = mid-1
        else:
            lo = mid+1
    return hi


def num_nonoverlapping(classes):
    classes.sort(key=lambda x: x[1])
    dp = [0] * len(classes)
    prefix_sum = defaultdict(int)
    dp[0] = 1
    prefix_sum[0] = 1

    for i in range(1, len(classes)):
        start = classes[i][0]
        best = bin_search(classes, start)
        dp[i] = 1 + prefix_sum[best]
        prefix_sum[i] = dp[i] + prefix_sum[i-1]
    return sum(dp)


def format_ans(ans):
    s = str(ans)
    if len(s) >= 8:
        return s[len(s)-8:]
    else:
        return (8-len(s)) * "0" + s


while True:
    n = int(input())
    classes = []
    if n == - 1:
        break

    for _ in range(n):
        start, end = map(int, input().split())
        classes.append((start, end))

    ans = num_nonoverlapping(classes)
    print(format_ans(ans))

I’m getting a TLE I’d love some pointers on how I could make this faster