机场调度器

Question

这就是问题所在：

机场假装我们在运营一个只有一条跑道的小型机场。我们需要开发一个数据结构来帮助安排飞机从这条跑道起飞和降落。每次飞机起飞或降落时，都需要在预定跑道使用前10分钟开始专用跑道，在预定跑道使用后10分钟结束(假设实际起飞或降落是瞬时的)。您的任务是使用大约以下API实现调度程序:如果有“时间”CouldScheduleAt(日期时间)调度的空间，则类scheduler { //返回true；如果成功地调度了ScheduleAt(日期时间)，//返回true；//选择调度的可用时间，然后返回该时间计划()；//如果成功地取消调度，则返回true；}请确保飞机没有重叠的计划。如果时间允许，写一个测试。

这是我的解决方案：

"use strict";

/* to make it, i create an array with the possible minutes where you can set
 a selected plane to use the runway, and i use this array to check if the plane
 can use it.
*/
class Scheduler {
   constructor() {
    this.minutes = [];
    this.maxMinutesDay = 1439; // the 1440 is equal to the 0
  }

// returns true if there’s room to schedule at ‘time’
   CouldScheduleAt(dateTime) {
      let totalMinutes = dateTime.getHours() * 60 + dateTime.getMinutes();
      if (totalMinutes < 10) return false;
      if(this.minutes[totalMinutes - 10] || this.minutes[totalMinutes + 9]) return false
      return true;
   }

// returns true if we successfully scheduled
   ScheduleAt(dateTime) {
      if(!this.CouldScheduleAt(dateTime)) return false;
      let totalMinutes = dateTime.getHours() * 60 + dateTime.getMinutes();
      let upperLimit = totalMinutes + 9;
      for(var i = totalMinutes - 10; i <= upperLimit; i++){
         this.minutes[i] = totalMinutes;
      }
      return true;
   };

// Choose an available time to schedule at, and return that time
   Schedule() {
      var i = 0;
      var finalMinute = false;
      var currentFreeMinutes = 0;
      while(i < this.maxMinutesDay - 10) {
         if(!this.minutes[i]) {
            currentFreeMinutes++;
            if(currentFreeMinutes == 20) {
               finalMinute = i - 9;
               break;
            }
            i++;
         } else {
            //I found a schedule
            currentFreeMinutes = 0;
            i += 20; //so I go forward 20 minutes
         }
      }
      var date = new Date();
      date.setHours(0, 0, 0);
      date.setMinutes(finalMinute);
      return date;
   };

// returns true if we successfully unscheduled something
   UnscheduleAt(dateTime) {
      let totalMinutes = dateTime.getHours() * 60 + dateTime.getMinutes();
      if(!(this.minutes[totalMinutes] === totalMinutes)) return false;
      let upperLimit = totalMinutes + 9;
      for(var i = totalMinutes - 10; i <= upperLimit; i++){
         this.minutes[i] = false;
      }
      return true;
   };
}

module.exports = Scheduler;

Answer 1

我不明白为什么你在这里加了一个单日的边界，而这不是问题中提到的东西。你真的一次只能安排一天吗？

您目前的方法不允许您跨越一天的界限，也不允许您在23:50:00和00:09:59之间安排任何航班，这似乎是有问题的。至少，如果您不想在00:10:00之前安排航班，这意味着您应该绝对能够安排到23:59:59的航班(因为您在午夜后自动给自己10分钟的缓冲区)。

您的数据结构对于Schedule()用例来说并不是最优的，因为在这种情况下，确定插入点不是确定某个东西是否已经阻止了该位置的问题。我确实认为，由于您在计划中只有一天的时间限制，这可能并不重要，但假设您决定修改此计划以适应未来的时间，并且假设您希望执行一项操作以确定您可以在少于O(n)时间内在日程中放置某项内容，您可能需要考虑实现某种树(即B-树、二进制搜索树或类似的树)或图形结构来优化这个用例。

根据类中所有方法的预期读/写比率，您甚至可能会发现维护多个数据结构很有用，以便在可能的情况下提供O(1)读取，就像您现在所做的一样，以及为Schedule()用例提供O(log )查找。当然，这将以更昂贵的写作代价为代价。

关于守则本身的一些想法：

• 您正在不一致地使用var和let。由于您使用的是ES6，我想说您也错过了使用常量的机会。
• maxMinutesDay没有理由成为实例变量。
• 您可以考虑将对适用方法的参数输入验证为有效的Date对象实例。
• 实际上，在这里我会使用更常见的javascript语法，而不是对您的方法名使用初始上限(在这方面，“近似API”可能是个小问题)。
• 为什么硬代码10分钟作为事件周围的时间缓冲区？这可以很容易地传递给构造函数来覆盖默认值。
• 您使用严格和松散的比较不一致。除非有特定的理由使用松散的比较，否则您应该使用严格的比较作为默认。
• 可能有机会重构添加方法来写入/删除一段时间(大约给定的事件时间)，并删除一些不必要的变量声明，但这可能是一分为二的，因为您所拥有的内容通常是可读的，并且实现起来很明智。