对链表进行排序，将一些元素打包在一起

Question

我有一个链接列表：

MyLinkedList::LinkedList<Event *> list;

其中

LinkedList

来自 this 库，

Event

是这个结构：

typedef struct 
{
    TimeSpan time;
    int value;

    bool queued;
} Event;

其中

TimeSpan

来自 this 库。 用一些项目填充列表后，我运行以下函数：

bool Events::Save()
{
    // order the elements by the time
    _listEvents.sort(compare);

    // open a file for writing    

    for (int i = 0; i < _listEvents.size(); i++)
    {
        Event *event = _listEvents.get(i);
        // write the item to the file
        writeEvent(file, *event);
    }

    file.close();
    return true;
}

compare

函数定义如下：

int compare(Event *&ev1, Event *&ev2)
{
    if (ev1->time.hours() > ev2->time.hours()) return true;
    if (ev1->time.hours() < ev2->time.hours()) return false;
    return (ev1->time.minutes() > ev2->time.minutes());
}

它只是按时间对元素进行排序。 这段代码运行良好。

现在我需要处理结构中的

queued

标志。 这里是一个示例输入数据：

时间	价值	排队
18:00	1	假
xx:xx	2	真实
xx:xx	3	真实
10:30	4	假
xx:xx	5	真实
08:15	6	假
06:45	7	假

排序时，设置了

queued

标志的项目 必须位于前一个项目之后（设置了

queued

未），无论其时间值如何（因此表中的

xx:xx

）。

预期输出是：

时间	价值	已排队
06:45	7	假
08:15	6	假
10:30	4	假
xx:xx	5	真实
18:00	1	假
xx:xx	2	真实
xx:xx	3	真实

换句话说：如果

queued

是

false

，则元素将照常排序（按时间），如果

true

，它们必须遵循前一个元素（就像它们“分组”在一起）。

由于

compare

函数只能处理两个项目，并且除了初始订单之外我没有其他信息，因此如何将

queued

项目与其“父”项目一起保留？

Answer 1

首先对您的列表进行分组。在您的示例中，

[1, 2, 3, 4, 5, 6, 7]

变为

[[1, 2, 3], [4, 5], [6], [7]]

。

然后按每组中第一个元素的时间戳对它们进行排序。

然后压平该列表。