How to improve my algorithm for a stick length problem

Viewed 28

I have this typical code interview type problem.

Suppose you have a stick of length n. You make X cuts in the stick at places x1, x2, x3 and so on. For every cut in X cuts you need to print the length of current longest piece.

Here is my current code:

# first for every cut in list of cuts split an element in thing
n, m = [int(x) for x in str(input()).split()]

sticks = [0,n] # the whole stick without cuts
cuts = [int(x) for x in str(input()).split()]
biggestrange = [0,n]
maximum = n
for j in range(m):
    cut = cuts[j]

    i = 0
    while sticks[i] < cut:
        i += 1

    sticks.insert(i,cut)
    if biggestrange[0]<cut and cut<biggestrange[1]:
        # we need to calculate the biggest range again
        
        maximum = 0
        for counter in range(len(sticks)-1):
            value = sticks[counter+1]-sticks[counter]
            #print(value)
            if value > maximum:
                maximum = value
        

    #print(sticks)
    print(maximum)

The code works but I do not know of a more efficient way to solve this problem and my code doesn't run in the required time frame. Thanks in advance for the help!

Edit: fixed indentation problem.

0 Answers
Related