计划之间差距的想法

Question

我卡在我的代码上，没有任何想法。

我有一个：

QList<QPair<QTime,QTime>> data;

我的 QPair 表示初始时间、结束时间，这基本上是安排某事的时间范围。

我有这个 Qlist 是为了知道我在特定的一天有什么时间表。

我需要知道什么是空闲时间，但我运行不知道如何做到这一点。我首先制作一个 Qlist，根据时间表将所有内容放在同一个地方，然后订购该 Qlist。

Answer 1

首先，QPair 不是一个描述性很强的类型。拥有自己的结构是有意义的：

// https://github.com/KubaO/Whosebugn/tree/master/questions/schedule-gap-54294739
#include <QtCore>
#include <type_traits>

struct Block {
   QTime start, end;
   enum class Kind { Null, Available, Busy } kind = Kind::Null;
   Block() = default;
   Block(const Block &) = default;
   Block(const QTime &start, const QTime &end, Block::Kind kind)
       : start(start), end(end), kind(kind) {
      Q_ASSERT(start <= end);
   }
};

由于所有操作都最简单地对单个事件执行，而不是对事件对的块，所以我们也有一个单个事件的表示。该事件指示可能可用或忙碌的一段时间的开始或结束。可用性或繁忙度是单独考虑的。 available 成员表示可用性块开始 (1) 或结束 (-1)。 busy 成员类似地表示一段忙碌时间开始 (1) 或结束 (-1)。

class Event {
  public:
   int available = 0, busy = 0;
   QTime time;
   enum class Kind { Null, BeginAvailable, EndAvailable, BeginBusy, EndBusy };
   Event() = default;
   Event(const QTime &time, Kind kind)
       : available(kind == Kind::BeginAvailable ? +1
                                                : kind == Kind::EndAvailable ? -1 : 0),
         busy(kind == Kind::BeginBusy ? +1 : kind == Kind::EndBusy ? -1 : 0),
         time(time) {}
   Block::Kind blockKind() const {
      return available ? Block::Kind::Available
                       : busy ? Block::Kind::Busy : Block::Kind::Null;
   }
};

然后你会想要根据开始时间对块进行排序，加入重叠的块，然后根据所需的操作合并它们。你想从可用时间中减去繁忙时间，所以寻求的输出是“AvailableNotBusy”：时间段必须是原来可用的，并且不与繁忙时间重叠。

using Blocks = QVector<Block>;
using Events = QVector<Event>;

Events eventsFromBlocks(const Blocks &);
Events sortedEvents(const Events &);
enum class MergeOp { Available, Busy, AvailableNotBusy, BusyNotAvailable };
Events mergeEvents(const Events &, MergeOp);
Blocks blocksFromEvents(const Events &);

Blocks mergeBlocks(const Blocks &a, const Blocks &b, MergeOp op) {
   auto events = eventsFromBlocks(a);
   events.append(eventsFromBlocks(b));
   events = sortedEvents(std::move(events));
   events = mergeEvents(std::move(events), op);
   return blocksFromEvents(std::move(events));
}

Schedule sortSchedule(const Schedule &);
Schedule joinOverlapping(const Schedule &);
Schedule subtract(const Schedule &, const Schedule &);

例如，要获得空闲时间，您需要所有可用且不忙的时间块：

Blocks freeSchedule(const Blocks &a, const Blocks &b) {
   return mergeBlocks(a, b, MergeOp::AvailableNotBusy);
}

Blocks freeWorkSchedule(const Blocks &busy) {
   return freeSchedule({{{8, 0}, {17, 0}, Block::Kind::Available}}, busy);
}

块和事件之间的转换是相当机械的：

Events eventsFromBlocks(const Blocks &schedule) {
   Events events;
   events.reserve(schedule.size() * 2);
   for (auto &block : schedule) {
      if (block.kind == Block::Kind::Available) {
         events.push_back({block.start, Event::Kind::BeginAvailable});
         events.push_back({block.end, Event::Kind::EndAvailable});
      } else if (block.kind == Block::Kind::Busy) {
         events.push_back({block.start, Event::Kind::BeginBusy});
         events.push_back({block.end, Event::Kind::EndBusy});
      }
   }
   return events;
}

Blocks blocksFromEvents(const Events &events) {
   Blocks blocks;
   blocks.reserve(events.size() / 2);
   bool start = true;
   for (auto &event : events) {
      if (start) {
         blocks.push_back({event.time, {}, event.blockKind()});
      } else {
         blocks.back().end = event.time;
         Q_ASSERT(blocks.back().kind == event.blockKind());
      }
      start = !start;
   }
   return blocks;
}

事件按时间排序：

Events sortedEvents(const Events &events) {
   Events sorted = events;
   std::sort(sorted.begin(), sorted.end(),
             [](const Event &a, const Event &b) { return a.time < b.time; });
   return sorted;
}

现在，为了合并事件，我们按时间顺序遍历它们，同时跟踪我们是否在任何时候处于可用时段内，and/or 处于繁忙时段内。这分别由运行总和 available 和 busy 的非零值表示。这些总和的值表示在任何给定时间有多少给定类型的块重叠。例如。 busy==3 表示我们在 3 个重叠的繁忙街区内。确定我们得到什么输出的操作采用运行总和的当前值。只要操作结果在经过某个时间点后发生变化，结果就会作为合并事件转储。重叠的事件时间仅通过查找离开时间点后 operation 结果的变化来处理。事件的 recessiveKind 是我们开始的默认事件类型。操作结果的第一个远离该事件类型的更改将导致发出第一个事件。

注意：此代码中可能存在错误:)

template <typename Op>
std::enable_if_t<std::is_invocable_r_v<Event::Kind, Op, int, int>, Events> mergeEvents(
    const Events &events, Event::Kind recessiveKind, Op operation) {
   Events merged;
   QTime prevTime;
   Event::Kind prevState = recessiveKind;
   int available = 0, busy = 0;
   for (auto ev = events.begin();; ev++) {
      if (ev != events.end()) {
         available += ev->available;
         busy += ev->busy;
      }
      Q_ASSERT(available >= 0);
      Q_ASSERT(busy >= 0);
      if (ev == events.end() || (ev != events.begin() && prevTime != ev->time)) {
         Event::Kind state = operation(available, busy);
         if (prevState != state) {
            merged.push_back({ev->time, state});
            prevState = state;
         }
         prevTime = time;
      }
   }
   return events;
}

您可能希望执行一些常见操作：

MergeOp::Available：仅提取与可用性相关的事件，忽略忙碌。
MergeOp::Busy：仅提取与忙碌相关的事件，忽略可用性。
MergeOp::AvailableNotBusy: 当(available && !busy)状态改变时提取事件。
MergeOp::BusyNotAvailable: 当(busy && !available)状态改变时提取事件。

Events mergeEvents(const Events &events, MergeOp op) {
   switch (op) {
      case MergeOp::Available:
         return mergeEvents(events, Event::Kind::EndAvailable, [](int a, int) {
            return a ? Event::Kind::BeginAvailable : Event::Kind::EndAvailable;
         });
      case MergeOp::AvailableNotBusy:
         return mergeEvents(events, Event::Kind::EndAvailable, [](int a, int b) {
            return (a && !b) ? Event::Kind::BeginAvailable : Event::Kind::EndAvailable;
         });
      case MergeOp::Busy:
         return mergeEvents(events, Event::Kind::EndBusy, [](int, int b) {
            return b ? Event::Kind::BeginBusy : Event::Kind::EndBusy;
         });
      case MergeOp::BusyNotAvailable:
         return mergeEvents(events, Event::Kind::EndBusy, [](int a, int b) {
            return (b && !a) ? Event::Kind::BeginBusy : Event::Kind::EndBusy;
         });
   }
}

计划之间差距的想法

Idea for gap between schedules

c++

qt

qlist

qtime