https://www.acmicpc.net/problem/2170
initial
finding the length of connected points
If the nextX<=end<=nextY, that means we can simply extend our current line by updating value of end to nextY or itself whichever is bigger.
But I forgot one fundamental logic, as impl in the elif part in solution. If
3
1 6
2 3
4 5
the nextX and nextY is within the boundary of start and end, then we do nothing and continue. If I didnt take care of this logic, then it would go to the else statement and update answer wrongly
solution
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
lst = [list(map(int,input().split())) for _ in range(n)]
lst.sort(key=lambda x:x[0])
start,end = lst[0][0],lst[0][1]
count=0
for i in range(1,n):
nextX,nextY=lst[i][0],lst[i][1]
if nextX<=end<=nextY:
end=max(end,nextY)
## i forgot this elif logic
elif start<=nextX<=end and start<=nextY<=end:
continue
else:
count+=end-start
start=nextX
end=nextY
count+=end-start
print(count)complexity
i thought it is o(n) but i use max() in the for loop and max is o(n) so is it n^2? no I keep forgetting sort time which is n log n
The max() function inside the for loop is called for each pair of intervals (current interval and the next one). This operation has a time complexity of O(1) because it simply compares two numbers and returns the maximum.
The time complexity of this code is O(n log(n)), where n is the number of intervals in the list lst. The sorting step takes O(n log(n)) time, and then the code iterates through the sorted list once, which takes O(n) time. Therefore, the dominant term is the sorting step.
The space complexity of this code is O(n) because it stores the input intervals in the list lst, and it uses a constant amount of additional memory for variables like start, end, and count.
So, the code has a time complexity of O(n * log(n)) and a space complexity of O(n).
