Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Python TLE for Activities (Spoj)
Difference between en1 and en2, changed 1 character(s)
I am trying to sovle 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 :frowning: I’d love some pointers on how I could make this faster↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English pfft 2019-12-13 21:39:03 1
en1 English pfft 2019-12-13 21:38:34 1444 Initial revision (published)