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 無題.png

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

Interval scheduling learning memo ~ by python ~
Python & Machine Learning Study Memo ④: Machine Learning by Backpropagation
Python class (Python learning memo ⑦)
Python module (Python learning memo ④)
[Python] Interval scheduling ABC103D
Visualization memo by Python
Python learning memo for machine learning by Chainer from Chapter 2
Python learning memo for machine learning by Chainer Chapters 1 and 2
Python control syntax, functions (Python learning memo ②)
Python memo
python memo
Machine learning summary by Python beginners
Python memo
python learning
Python learning memo for machine learning by Chainer Chapter 7 Regression analysis
Python memo
"Scraping & machine learning with Python" Learning memo
Python memo
Python memo
Python learning memo for machine learning by Chainer Chapter 8 Introduction to Numpy
Python learning memo for machine learning by Chainer Chapter 9 Introduction to scikit-learn
Python numbers, strings, list types (Python learning memo ①)
Ant book in python: page 43 Interval scheduling
Python standard library: second half (Python learning memo ⑨)
Python & Machine Learning Study Memo ③: Neural Network
Python & Machine Learning Study Memo ⑥: Number Recognition
Python standard library: First half (Python learning memo ⑧)
[Python] Memo dictionary
LPIC201 learning memo
[Python] Learning Note 1
python beginner memo (9.2-10)
Python learning notes
Python learning memo for machine learning by Chainer Chapter 13 Neural network training ~ Chainer completed
Django Learning Memo
python beginner memo (9.1)
python learning output
Python learning site
★ Memo ★ Python Iroha
Python learning day 4
[Python] EDA memo
Python Deep Learning
Python 3 operator memo
Python learning (supplement)
Deep learning × Python
[Memo] Machine learning
Python learning memo for machine learning by Chainer Chapter 13 Basics of neural networks
[My memo] python
Python3 metaclass memo
[Python] Basemap memo
Python learning memo for machine learning by Chainer until the end of Chapter 2
Python beginner memo (2)
python learning notes
[Python] Numpy memo
Python & Machine Learning Study Memo ⑤: Classification of irises
Python & Machine Learning Study Memo ②: Introduction of Library
Video frame interpolation by deep learning Part1 [Python]
A memo for creating a python environment by a beginner
progate Python learning memo (updated from time to time)
Python & Machine Learning Study Memo ⑦: Stock Price Forecast
Primality test by Python
[Keras] Personal memo to classify images by folder [Python]