My take on the algorithmic crush problem from HackerRank

Question

This is my solution to the Algorithmic Crush problem from HackerRank. Can I get any comments regarding where I can improve the code to be more efficient?

You are given a list of size \$N\$, initialized with zeroes. You have to perform \$M\$ operations on the list and output the maximum of final values of all the \$N\$ elements in the list. For every operation, you are given three integers \$a, b\$ and \$k\$ and you have to add value to all the elements ranging from index \$a\$ to \$b\$ (both inclusive).

Input Format

First line will contain two integers \$N\$ and \$M\$ separated by a single space. Next \$M\$ lines will contain three integers \$a, b\$ and \$k\$ separated by a single space. Numbers in list are numbered from \$1\$ to \$N\$.

Constraints

\$3 \leq N \leq 10^7\$

\$1\leq M \leq 2*10^5\$

\$1 \leq a \leq b \leq N\$

\$ 0 \leq k \leq 10^9\$

Output Format

A single line containing maximum value in the updated list.

Sample Input

5 3
1 2 100
2 5 100
3 4 100

Sample Output

200

def updateList(seq, listA):
    st, end, value = map(int, seq.split())
    for i in range(st-1, end):
        listA[i] = listA[i]+value
    return listA

n, m = map(int, raw_input().split())

lis = [0 for i in range(n)]

for ins in range(m):
    cmds = raw_input()
    resultSet = updateList(cmds, lis)
    lis = resultSet
print sorted(resultSet)[-1]

Answer 1

The code is generally clean, however, maintaining the same algorithm will probably result in a timeout for this problem. Your current complexity is \$ O(N\cdot M) \$ which could be up to \$ 10^7 \times 10^5 \$ according to the problem statement.

A similar problem to this is the maximum interval overlap problem, discussed here. The problem is given the guest arrival and departure times in a party, find the interval with the maximum guests. It should be a good exercise to apply the same idea to this problem.