https://www.acmicpc.net/problem/1946
initial
Well I knew we had to sort the given list but i wasnt sure how to implement the logic. Lets define A score as the score in 0th index and B score as the score in 1st index. If we have the smallest A score, then what? do we compare for each iter element with other elements?
Actually we dont have to compare for each iter. Since we have sorted the list and the first element in the list is guaranteed to have the lowest A score, if any other elements in the list have a lower B score than this element, then the condition is met.
my wrong code
t=int(input())
for _ in range(t):
n = int(input())
lst=[]
for _ in range(n):
a,b = map(int,input().split())
lst.append([a,b])
lst.sort(key=lambda x:(x[0],x[1]))
ans=0
count=0
minA,minB = int(10e9),int(10e9)
for hola in lst:
a,b=hola
if a>=minA and b>=minB:
count=1
minA,minB = a,b
continue
else:
count+=1
minA=min(minA,a)
minB=min(minB,b)
ans=max(ans,count)
print(ans)solution
import sys
input = sys.stdin.readline
t=int(input())
for _ in range(t):
n = int(input())
lst=[]
for _ in range(n):
a,b = map(int,input().split())
lst.append([a,b])
lst.sort(key=lambda x:x[0])
ans=1
maxA=lst[0][1]
for i in range(len(lst)):
if lst[i][1]<maxA:
ans+=1
maxA=lst[i][1]
print(ans)complexity
n log n cuz sort? oops i forgot our code runs for multiple test cases so the time is tn log n.
n space
Time Complexity:
The outer loop runs in O(t) time.
Reading each test case involves reading n intervals and sorting them, which takes O(n log(n)) time.
The inner loop runs in O(n) time.
The overall time complexity is dominated by the sorting operation, so it is O(t n * log(n)).
Space Complexity:
The space complexity is O(n) for the lst list.
Your code is efficient, and its time complexity is reasonable for the given problem.
