-1

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

我有一个 ：

QList<QPair<QTime,QTime>> data;

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

我有这个 Qlist 是为了了解我在特定日期有哪些日程安排。

我需要知道什么是空闲时间，而我对如何做到这一点一无所知。我首先制作一个 Qlist，按照时间表将所有内容放在同一个地方，然后订购该 Qlist。

4

1 回答 1

2

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

// https://github.com/KubaO/stackoverflown/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;
}

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

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

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;
         });
   }
}
于 2019-01-22T05:27:33.590 回答