2554. Maximum Number of Integers to Choose From a Range I  

Simple greedy.

Complexity

  • Time complexity: $O(N)$
  • Space complexity: $O(M)$

Code

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned = set(banned)
        cur_sum = 0
        cnt = 0
        for i in range(1, n + 1):
            if i in banned:
                continue
            if cur_sum + i > maxSum:
                return cnt
            cur_sum += i
            cnt += 1
        return cnt