5
\$\begingroup\$

This is the problem:

Airport

Pretend we are operating a small airport with a single runway. We need to develop a data structure to help scheduling airplanes to take off and land from this runway. Each time a plane takes off or lands, it needs exclusive use of the runway starting 10 minutes before the scheduled runway use, and ending 10 minutes after the scheduled runway use (assume the actual take-off or landing is instantaneous).

Your task is to implement a scheduler with approximately the following API:

 class Scheduler {
 // returns true if there’s room to schedule at ‘time’
 CouldScheduleAt(Date time);

 // returns true if we successfully scheduled
 ScheduleAt(Date time);

 // Choose an available time to schedule at, and return that time
 Schedule();

 // returns true if we successfully unscheduled something
 UnscheduleAt(Date time);
}

Be sure that planes don’t have overlapping schedules. If time permits, write a test for this.

Here is my solution:

"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;
\$\endgroup\$
  • 1
    \$\begingroup\$ Interesting solution with O(1) lookup time. Summer / winter time shift and leap minutes might pose a problem as well as very busy days where the next available time slot is more than 24 hours ahead. I would prefer keeping a sorted list / tree of starting times with log(n) lookup times but more robust date comparisons. \$\endgroup\$ – le_m Mar 28 '17 at 0:01
1
\$\begingroup\$

I don't understand why you imposed a single day boundary here when this is not something that is presented in the question. You can really only schedule one day at a time?

Your current methodology which doesn't allow you to cross day boundaries will not let you schedule any flights between 23:50:00 and 00:09:59, which seems problematic. At a minimum, if you didn't want to schedule flights before 00:10:00 this means you should absolutely be able to schedule flights up to 23:59:59 (since you automatically give yourself the 10 minute buffer after midnight).


Your data structure is not optimal for the Schedule() use case where determining a point of insertion is not a matter of determining whether something already blocks that position. I do suppose that with the limitation you have placed of only having a single day in the schedule, this might not be important, but assuming that you decided to modify this schedule to accommodate times well out in the future, and assuming that you want to perform an operation to determine where you can fit something in the schedule in less than O(n) time, you might need to look at implementing some sort of a tree (i.e. B-tree, Binary search tree, or similar) or graph structure to best optimize this use case.

Depending on expected ratio of reads vs. writes across all methods in the class, one might even find it useful to maintain multiple data structures to provide O(1) reads where possible like you are doing now as well as O(log n) lookups for the Schedule() use case. This of course would come at the cost of more expensive writes.


Some thoughts on the code itself:

  • You are using var and let inconsistently. And since you are using ES6, I would say you are missing opportunities to use constants as well.
  • There is no reason maxMinutesDay should be an instance variable.
  • You might consider validating parametric input to applicable methods as being valid Date object instances.
  • I would actually use more common javascript syntax here and not use initial caps on your method names (perhaps "approximate API" was a bit of a gotcha in this regard).
  • Why hard-code 10 minutes as the time buffer around the events? This could easily be passed to constructor to override default.
  • You use strict and loose comparisons inconsistently. You should prbably use strict comparisons as default unless there is a specific reason to use loose comparisons.
  • There are probably opportunities to refactor to add methods to write/delete a block of time (around given event time) and remove some unnecessary variable declarations, but this might be splitting hairs, as what you have is generally readable and sensibly implemented.
\$\endgroup\$
  • \$\begingroup\$ Thanks, i selected the 1 day limit, to take into consideration the Schedule() method, because when i did it, i thought it would be hard to search a date available. I searched for the next date available, and not any date. Could you tell me how would you do the Schedule() function with some code? \$\endgroup\$ – Gaunt Mar 29 '17 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.