I am trying to solve this question called Concert tickets from cses problem set. Link.
From what I have understood, I need to find the lower bound for each element for customer's array from the ticket price array. If the lower bound exists, I need to pop that element from the tickets array, else print -1. My current approach is to use the standard list with a binary search function to find the equal or maximum smallest element in the array, if it exists. The code is here :
n ,m = map(int ,input().split())
tickets = list(map(int ,input().split()))
maxprice = list(map(int ,input().split()))
tickets.sort()
def binary(arr ,target):
left = 0
ans = -1
ansi = -1
mid=0
right = len(arr) - 1;
while left <= right:
mid = left +(right-left)//2;
if arr[mid] > target:
right = mid-1
elif mid < target:
ans = arr[mid]
ansi = mid
left = mid+1
else:
return arr[mid] ,mid
return ans ,ansi
for item in maxprice:
ans ,i = binary(tickets ,item)
print(ans)
if ans != -1:
tickets.pop(i)
This approach is giving me TLE for large inputs (n > 10^5), which I am assuming is due to the expensive pop operation on list at the last line. Kindly help to optimize this code.
