https://www.acmicpc.net/problem/1263
initial
I thought of this greedy question like the minimum number of arrows to burst balloons. I tried thinking bottom-up where I would be processing the data with earliest end times. But not
n=int(input())
Graph = [list(map(int,input().split()) for _ in range(n)]
graph.sort(key=lambda x:x[1],x[0])
Tmp = int(10e6)
right=0
ans=0
For i in graph:
Dur,end = i
Sleep_time = end-dur
If sleep_time>right:
right=sleep_time
Else:
If sleep_time-dur<=0:
print(-1)
exit()
Else:
sleep_time-=dur
print(sleep_time)
solution
https://baby-ohgu.tistory.com/47
This is going top down so reverse sort of end times. We initialise a variable for our sleeping time for the first value in the list by subtracting duration from end time. Next, we iterate through the other elements and if the sleeping time (e.g 15) is greater or equal than the end time of that data (e.g.14), That means we have to initalise a new sleeping time that takes into account this current task and that requires less sleep. So the new sleeping time will be current task's end date - current task's duration.
Else, if the sleeping time (15) is less than current task's ending time (17), that means we have to finish this current task by 17 so sleeping time at 15 is impossible. We have to sacrifice sleep and do this task so we minus our sleeping time via the duration of this current task to still sleep in as much as possible.
import sys
input = sys.stdin.readline
n=int(input())
graph = [list(map(int,input().split()) )for _ in range(n)]
graph.sort(key = lambda x: x[1], reverse=True)
ans = graph[0][1]-graph[0][0]
for i in range(1,n):
if graph[i][1]>=ans:
ans-=graph[i][0]
else:
ans=graph[i][1]-graph[i][0]
print(ans) if ans >= 0 else print(-1)
revisited jan 25th
yes i retried and since we need to find the starting time when to wake up, we need to REVERSE sort the ending time and reduce the waking time as we iter through the tasks.
complexity
n log n time cuz sort and n space
