Donné est un tableau avec n projets. Chaque projet peut contenir n tâches non triées. Échantillon:
projects = [
{"name" : "Sampleproject 1", "tasks" :
{"order" : 1, "description" : "Do something 1", "status" : "Done"},
{"order" : 3, "description" : "Do something 3", "status" : "Open"},
{"order" : 2, "description" : "Do something 2", "status" : "Open"}
},
{"name" : "Sampleproject 2", "tasks" :
{"order" : 1, "description" : "Do something 1", "status" : "Done"},
{"order" : 1, "description" : "Do something 3", "status" : "Open"},
{"order" : 1, "description" : "Do something 2", "status" : "Open"},
{"order" : 2, "description" : "Do something 4", "status" : "Open"}
}
]
Je dois ajouter une clé active pour chaque tâche, si elle peut être traitée par l'utilisateur.
Les tâches peuvent être traitées parallèlement et séquentiellement, représentées par le numéro de commande. Cela signifie: Toutes les tâches avec le numéro d'ordre 1 doivent être effectuées avant qu'une tâche avec l'ordre 2 puisse être traitée, toutes les prises avec le numéro d'ordre 2 doivent être effectuées avant que 3 puisse être traitée, et ainsi de suite ...
Sortie requise:
projects = [
{"name" : "Sampleproject 1", "tasks" :
{"order" : 1, "description" : "Do something 1", "status" : "Done", "active" : false},
{"order" : 3, "description" : "Do something 3", "status" : "Open", "active" : false},
{"order" : 2, "description" : "Do something 2", "status" : "Open", "active" : true}
},
{"name" : "Sampleproject 2", "tasks" :
{"order" : 1, "description" : "Do something 1", "status" : "Done", "active" : false},
{"order" : 1, "description" : "Do something 3", "status" : "Open", "active" : true},
{"order" : 1, "description" : "Do something 2", "status" : "Open", "active" : true},
{"order" : 2, "description" : "Do something 4", "status" : "Open", "active" : false}
}
]
3 réponses
Ce n'est pas la solution la plus efficace, mais vous pouvez trier les tâches par order, puis définir l'ordre de priorité le plus récent avec l'état Open sur active et le reste sur false . La complexité temporelle est probablement O(P * TLog(T) + T), qui peut être simplifiée à simplement O(P * TLog(T)), où P est le nombre de projets et T est le nombre de tâches par projet. Le tri est NLog(N), c'est donc d'où vient le TLog(T).
from operator import itemgetter
from json import dumps
projects = [
{
"name": "Sampleproject 1",
"tasks": [
{"order": 1, "description": "Do something 1", "status": "Done"},
{"order": 3, "description": "Do something 3", "status": "Open"},
{"order": 2, "description": "Do something 2", "status": "Open"},
],
},
{
"name": "Sampleproject 2",
"tasks": [
{"order": 1, "description": "Do something 1", "status": "Done"},
{"order": 1, "description": "Do something 3", "status": "Open"},
{"order": 1, "description": "Do something 2", "status": "Open"},
{"order": 2, "description": "Do something 4", "status": "Open"},
],
},
]
for project in projects:
sorted_tasks = sorted(project["tasks"], key=itemgetter("order"))
priority_order = None
for task in sorted_tasks:
if task["status"] == "Open" and (priority_order is None or task["order"] == priority_order):
task["active"] = True
priority_order = task["order"]
else:
task["active"] = False
print(dumps(projects, indent=4))
Sortie en JSON (pour une visualisation plus facile du résultat):
[
{
"name": "Sampleproject 1",
"tasks": [
{
"order": 1,
"description": "Do something 1",
"status": "Done",
"active": false
},
{
"order": 3,
"description": "Do something 3",
"status": "Open",
"active": false
},
{
"order": 2,
"description": "Do something 2",
"status": "Open",
"active": true
}
]
},
{
"name": "Sampleproject 2",
"tasks": [
{
"order": 1,
"description": "Do something 1",
"status": "Done",
"active": false
},
{
"order": 1,
"description": "Do something 3",
"status": "Open",
"active": true
},
{
"order": 1,
"description": "Do something 2",
"status": "Open",
"active": true
},
{
"order": 2,
"description": "Do something 4",
"status": "Open",
"active": false
}
]
}
]
Une option consiste à utiliser un heap pour garder la trace de l'ordre le plus bas. Sur chaque tas, vous parcourez toutes les tâches et vous n'avez qu'à vérifier si la commande est celle à entretenir et si elle est ouverte. Cela ressemblerait à ceci:
In [25]: from heapq import heappush, heappop
In [26]: heap = []
In [27]: order_tracking = set()
In [28]: for project in projects:
...: for task in project['tasks']:
...: order_num = task['order']
...: if order_num not in order_tracking:
...: heappush(heap, order_num)
...: order_tracking.add(order_num)
...:
...:
In [29]: heap
Out[29]: [1, 3, 2]
Cela crée le tas minimum pour les numéros de commande. Il ne nous reste plus qu'à entretenir chacun:
In [31]: next_to_service = heappop(heap)
In [32]: for project in projects:
...: for task in project['tasks']:
...: order_num = task['order']
...: # If the order number matches
...: if order_num == next_to_service:
...: if task['status'] == 'Open':
...: task['active'] = 'true'
...: else:
...: task['active'] = 'false'
...: # Otherwise we can set it False
...: else:
...: task['active'] = 'false'
...:
Vous obtiendrez maintenant projects:
In [36]: pprint.pprint(projects)
[{'name': 'Sampleproject 1',
'tasks': [{'active': 'false',
'description': 'Do something 1',
'order': 1,
'status': 'Done'},
{'active': 'false',
'description': 'Do something 3',
'order': 3,
'status': 'Open'},
{'active': 'false',
'description': 'Do something 2',
'order': 2,
'status': 'Open'}]},
{'name': 'Sampleproject 2',
'tasks': [{'active': 'false',
'description': 'Do something 1',
'order': 1,
'status': 'Done'},
{'active': 'true',
'description': 'Do something 3',
'order': 1,
'status': 'Open'},
{'active': 'true',
'description': 'Do something 2',
'order': 1,
'status': 'Open'},
{'active': 'false',
'description': 'Do something 4',
'order': 2,
'status': 'Open'}]}]
Et puis parce que c'est un tas:
In [37]: heap
Out[37]: [2, 3]
Vous avez à nouveau le suivant à réparer au début. Et vous pouvez répéter le même processus de heappop jusqu'à ce que le tas soit vide et que toutes les commandes aient été traitées.
Nous parcourons la liste des tâches, en trouvant l'ordre minimum d'une tâche ouverte. Ensuite, nous parcourons à nouveau la liste et définissons ceux avec cet ordre sur active: true et le reste sur active: false
def add_active(project):
min_open = float("inf")
for t in project["tasks"]:
if t["status"] == "Open":
min_open = min(min_open, t["order"])
for t in project["tasks"]:
if t["status"] == "Open" and t["order"] == min_open:
t["active"] = "true"
else:
t["active"] = "false"
for p in projects:
add_active(p)
print(projects)