Mémo d'apprentissage de la planification des sections ~ par python ~

introduction

Mémo d'apprentissage sur le problème de planification de section de méthode gloutonne

problème

Concours de programmation Keyence 2020 "Bras de robot à problème B" 無題.png

Le problème de la sélection du plus grand nombre possible pour ceux qui ont des points de départ et d'arrivée fixes (problème d'ordonnancement de section) Résoudre avec une méthode gourmande La politique de base est de sélectionner le robot avec le plus petit point final parmi les robots qui peuvent être sélectionnés.

Répondre


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)

Commentaire

① Entrée


N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]

N est le nombre de robots XL est une liste de coordonnées X et de longueur de bras L

② Modifier la liste

Créez une liste (R) pour stocker le point de départ (a) et le point final (b) du bras du robot


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()

La liste R est triée par ordre croissant des points finaux

③ Planification et sortie des sections


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 est le nombre de robots sélectionnés con_l est le point final du bras du dernier robot sélectionné

Le traitement dans la boucle for est conçu pour rechercher avidement un robot avec un point de départ (R [i] [1]) plus grand que le point final (con_l) du dernier robot sélectionné. Puisque R est trié par ordre croissant des points finaux, celui avec le plus petit point final est toujours sélectionné lors de la recherche. Mettez à jour con_l en ajoutant +1 à ans à chaque fois qu'il est trouvé Sortie et finition

Résumé

C'était un problème typique de planification d'intervalle

Recommended Posts

Mémo d'apprentissage de la planification des sections ~ par python ~
Mémo d'étude Python & Machine Learning ④: Machine Learning par rétro-propagation
Classe Python (mémo d'apprentissage Python ⑦)
Module Python (mémo d'apprentissage Python ④)
Mémo de visualisation par Python
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer du chapitre 2
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer chapitres 1 et 2
Syntaxe de contrôle Python, fonctions (mémo d'apprentissage Python ②)
Mémo Python
mémo python
Résumé de l'apprentissage automatique par les débutants de Python
Mémo Python
apprentissage de python
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer Chapitre 7 Analyse de régression
Mémo Python
Mémo d'apprentissage "Scraping & Machine Learning avec Python"
Mémo Python
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer Chapitre 9 Introduction à scikit-learn
Numéros, chaînes, types de listes Python (mémo d'apprentissage Python ①)
Livre Ali en python: page 43 Planification des sections
Bibliothèque standard Python: seconde moitié (mémo d'apprentissage Python ⑨)
Mémo d'étude Python & Machine Learning ③: Réseau neuronal
Mémo d'étude Python & Machine Learning ⑥: Reconnaissance des nombres
Bibliothèque standard Python: première moitié (mémo d'apprentissage Python ⑧)
[Python] Mémo sur le dictionnaire
Note d'étude LPIC201
[Python] Note d'apprentissage 1
mémo débutant python (9.2-10)
Notes d'apprentissage Python
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer Chapitre 13 Formation sur les réseaux neuronaux ~ Chainer terminé
Mémo d'apprentissage Django
mémo débutant python (9.1)
sortie d'apprentissage python
Site d'apprentissage Python
★ Mémo ★ Python Iroha
Apprentissage Python jour 4
[Python] Mémo EDA
Apprentissage en profondeur Python
Mémo opérateur Python 3
apprentissage python (supplément)
Apprentissage profond × Python
[Memo] Apprentissage automatique
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer Chapitre 13 Bases du réseau neuronal
[Mon mémo] python
Mémo de métaclasse Python3
[Python] Mémo de fond de carte
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer jusqu'à la fin du chapitre 2
Mémo débutant Python (2)
notes d'apprentissage python
[Python] Mémo Numpy
Mémo d'étude Python & Machine Learning ⑤: Classification d'Ayame
Mémo d'étude Python & Machine Learning ②: Introduction de la bibliothèque
Interpolation d'images vidéo par apprentissage en profondeur, partie 1 [Python]
Notes sur la création d'un environnement python par les débutants
mémo d'apprentissage progate Python (mis à jour de temps en temps)
Mémo d'étude Python & Machine Learning ⑦: Prévision du cours de l'action
Jugement des nombres premiers par Python
[Keras] Mémo personnel pour classer les images par dossier [Python]