https://www.acmicpc.net/problem/1911
initial
We want to cover as much space with the planks, hoping that the leftover plank may cover other pools in our list so that we don't have to use planks to cover that space. So we first sort by the starting index of pools and use a end mark point to mark up to which point our planks have covered.
[Fixed oct 5th] So I made an absolute fatal misunderstanding between / and //. / is the float-point division whereas // is the floor devision. So 5/3 is 1.67 whilst 5//3 is 1. So math.ceil() which rounds up to the ceiling (literally) should take 5/3 decimal, not a whole number.
So we should do math.ceil(5/3)
import math
n, l = map(int, input().split())
ans = 0
mark = 0
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort(key=lambda x: x[0])
for interval in lst:
a, b = interval
mark = max(mark, a)
diff=b-mark
print(math.ceil(diff // l))
ans += math.ceil(diff // l)
print(ans)
mark = max(math.ceil((b - mark) / l) * l + mark, b)
print(ans)solution
fix it from // to / to get float
import math
n, l = map(int, input().split())
ans = 0
mark = 0
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort(key=lambda x: x[0])
for interval in lst:
a, b = interval
mark = max(mark, a)
diff=b-mark
ans += math.ceil(diff / l)
# print(ans)
mark = max(math.ceil((b - mark) / l) * l + mark, b)
print(ans)revisited jan 24th
thought of making a 1d visited list where the puddles will be marked as false. As we iterate from smallest starting index of puddle and up, if we see a False grid, we use a for loop of length l to make that visited[i:i+l] True. Will it work? i havent tried
but this math is cleaner and should be better in time.
(b - mark) / l) is number of planks
(b - mark) / l) l is total length of planks laid out to cover that puddle.
(b - mark) / l) l + mark is the ending point of plank, which might exceed end index of puddle so we need to update mark to be the biggest of the 2 for next puddle. If mark is greater than start index of next puddle, some of that puddle is already covered up.
