title: Efficient way to continually run interval scheduling algorithm
body: <p>I have a problem where I need to repeatedly run interval scheduling algorithm on a set of inputs that are streaming.</p>
  
  <p>For example imagine you have a stream of unsorted data for which you continuously get values over time. At the beginning let say I start with 8 intervals, I run interval schedule algorithm to get an output. </p>
  
  <p>Following is the code for the interval scheduling algorithm: </p>
  
  <pre class="lang-js prettyprint-override"><code>    class Job {
          constructor(start, finish, name) {
              this.start = start;
              this.finish = finish;
              this.name = name;
          }
      }
  
      function intervalScheduling(jobs) {
  
          jobs.sort((a, b) =&gt; {
              return a.finish - b.finish;
          })
  
          let jobsSelected = [];
          jobsSelected.push(jobs[0]);
  
          let lastJob = jobs[0];
  
          for(let i=0; i&lt;jobs.length;i++) {
              if (jobs[i].start &gt;= lastJob.finish) {
                  jobsSelected.push(jobs[i]);
                  lastJob = jobs[i];
              }
          }
  
          console.log(jobsSelected);
      }
  
      let jobs = [
          new Job(0, 6, "a"),
          new Job(1, 4, "b"),
          new Job(3, 5, "c"),
          new Job(3, 8, "d"),
          new Job(4, 7, "e"),
          new Job(5, 9, "f"),
          new Job(6, 10, "g"),
          new Job(8, 11, "h"),
      ];
  
      intervalScheduling(jobs);
  </code></pre>
  
  <p>I need to repeatedly call     <code>intervalScheduling(jobs);</code> with new set of jobs every one second.</p>
  
  <p>Since I will need to sort each time, the run time of the algorithm over the course of the program would be O(n^2 log n) because the runtime of the interval schedule algorithm is O(n log n) times the number of times I run it over time. Is there a way to use a better algorithm for this and get the run time to be lower?</p>
  
  <p>Thanks</p>