如何根据顺序检测列表中的下一个任务

Question

给定的是一个包含n个项目的数组。每个项目可以包含n个未排序的任务。样本：

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"}
    }
]

如果用户可以处理，我必须为每个任务添加一个活动键

任务可以并行和顺序处理，由订单号表示。这意味着：订单号为1的所有任务必须在处理订单号为2的任务之前完成，订单号为2的所有TAK必须在处理订单号为3的任务之前完成，依此类推

所需输出：

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}
    }
]

Answer 1

不是最有效的解决方案，但您可以按order对任务进行排序，然后将Open状态的最新优先级顺序设置为active，其余的设置为false。时间复杂度可能是O(P * TLog(T) + T)，可以简化为O(P * TLog(T))，其中P是项目数，T是每个项目的任务数。排序是NLog(N)，因此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))

输出为JSON（便于查看结果）：

[
    {
        "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
            }
        ]
    }
]

Answer 2

我们浏览任务列表，找到打开任务的最小顺序。然后，我们再次浏览列表，并将顺序设置为active: true，其余设置为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)

Answer 3

一种选择是使用heap来跟踪最低顺序。在每个heappop上，您将迭代所有任务，只需检查订单是否是要服务的订单，以及订单是否打开。这看起来像这样：

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]

这将建立订单号的最小堆。现在我们只需要为每一个提供服务：

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' 
...:                                                                                       

现在您将看到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'}]}]

然后因为它是一堆：

In [37]: heap                                                                                                                
Out[37]: [2, 3]

你有下一个服务在开始时再次。您可以重复相同的heappop过程，直到堆为空并且所有订单都得到了服务