Interval scheduling learning memo ~ by python ~
Introduction
Learning memo about the greedy algorithm interval scheduling problem
problem
"B Problem Robot Arms" of Keyence Programming Contest 2020
Problem of selecting as many as possible for those with fixed start and end points (interval scheduling problem) Solve with greedy algorithm The basic policy is to select the robot with the smallest end point among the robots that can be selected.
Answer
N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]
R=[]
for i in range(N):
a=max(0,XL[i][0]-XL[i][1])
b=XL[i][1]+XL[i][0]
R.append([b,a])
R.sort()
ans=0
con_l=0
for i in range(N):
if con_l <= R[i][1]:
ans += 1
con_l = R[i][0]
print(ans)
Commentary
① Input
N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]
N is the number of robots XL is a list of coordinates X and arm length L
② Edit the list
Create a list (R) to store the start point (a) and end point (b) of the robot arm
R=[]
for i in range(N):
a=max(0,XL[i][0]-XL[i][1])
b=XL[i][1]+XL[i][0]
R.append([b,a])
R.sort()
List R is sorted in ascending order of end points
③ Section scheduling & output
ans=0
con_l=0
for i in range(N):
if con_l <= R[i][1]:
ans += 1
con_l = R[i][0]
print(ans)
ans is the number of robots selected con_l is the end point of the last selected robot's arm
The processing in the for loop is designed to greedily search for a robot with a start point (R [i] [1]) larger than the end point (con_l) of the last selected robot. Since R is sorted in ascending order of end points, the one with the smallest end point is always selected during the search. Update con_l by adding +1 to ans each time it is found Output and finish
Summary
It was a typical interval scheduling problem
Recommended Posts