安装

npm install equiv-task-scheduler

导入

const TaskScheduler = require('equiv-task-scheduler')

对任意时间有优先级任务列表的调度(优先级高的尽可能的靠前)

/**
 * WMJsonTasks为任务列表
 * 每个任务有五个成员变量:name,start,end,exeTime,weight
 * 分别对应任务名,开始时间,结束时间,任务执行需要的时间,优先级
 * 数据格式如下：
 * [
 *  {
 *      name:'A',
 *      start:[-,2,7],
 *      end:[-,4,9],
 *      exeTime:2,
 *      weight:3
 *   },
 *  ...
 * ]
 * 开始和结束时间都是数组，0索引弃用，可以乱序（算法模块会进行排序），但不能出现脏数据，关于脏数据，详情见下方分时段算法的说明
 */

const WMResult =TaskScheduler.genWMResultVeryFirst(WMJsonTasks)
/**
 * WMResult[1:n]是返回的调度后的任务列表
 * WMResult[0]弃用
 */
console.log(WMResult)

数据结构(三种等价类)

1.基于数组的(未经过测试,也没有实际投入使用,谨慎使用它!)
2.基于伪链表的(经过测试,在1.0.10版本之前投入使用)
3.基于伪树的(经过测试,当前版本投入使用)

1.什么是分时段？

分时段是指一个任务可以被执行的时间段不一定是连续的。例如2:00开始4:00结束，随后7：00开始9：00结束。假设这个任务的执行时长是1h。那么在2-4，7-9之间的任何一个小时完成均认为成功。

2.如何排序？

2.1 先来看一个例子
    任务A有两个时间段,2:00-4:00,7:00-8:00;任务B只有一个时间段，7：00-8：00。那么此时虽然任务A的最大开始时间和任务B的最大开始时间一样，按理说先分配任务A即可。但是任务A一旦分配到7-8，那么任务B将无处可去。但显然任务A是可以分配到2-4的。
2.2 最小中的最大
    之所以成为“最小”中的“最大”，是因为我决定将每个任务的开始时间中的最小值拿出来，进行排序。依次调度拥有当前这群最小值中的最大值的任务。以2.1中的例子为例，实际上代表A的开始时间是2:00，而不是7：00。这样可以保证B先进行调度。
    而将最小值降序排列，可以保证那些开始时间靠后，比较紧张的任务可以优先调度。

3. 算法还可行吗？

待证明

4. 数据如何存储

我们可以将任务的start和end属性都改造为数组。(幸好JS是弱类型我想怎么定义怎么定义)然后将这两个数组都定义成小根堆(minHeap)。这样做的优点是，我可以分别对开始堆和结束堆进行push()，也就变相地同时对开始时间和结束时间做排序了。或者说，这样可以更容易的让结束时间跟随开始时间做排序。例如,[开始时间1，开始时间2]，[结束时间1，结束时间2]中，先对开始时间做排序，将两个时间交换，那么此时为了结束时间对应上开始时间，结束时间也应该伴随交换。但利用堆的push函数，我们可以轻易对两个堆进行维护，而不必在处理一个的同时惦记着另一个了。

5. 如何定义一个脏数据？

这其实延续了3的一个问题：凭什么分别维护小根堆可以保证开始时间和结束时间对应？因为我们不允许这样的情况出现：一个任务中，存在两个可执行时段，他们的交集不为空。例如，2：00-11：00和4：00-6：00，这是不被允许的，后者根本无需声明。而又例如，2：00-4：00和3：00-5：00，这也是不被允许的，因为完全可以写作2：00-5：00。任何一个可执行时段两两不相交的任务称为一个好数据。(如果它的其他数据也是好的)
然后这就解答了3的问题，如果有两个时段，其中的一个开始时间小于了另一个的结束时间，即，待push的开始时间发现比结束堆的top还要小的时候，一定产生了交集，不被允许push。而所有被允许push的，一定是一个的开始时间大于另一个的结束时间，而我们曾经就已经规定好了，一个时段的结束时间一定是大于其开始时间的。因此这一个的结束时间一定大于另一个的结束时间，也就是说，一个时段的开始时间和结束时间一定会被push到对应堆中的同一个位置。这样他们就可以对应上了。

6. 等价类合并操作时的条件

7.1 获取当前任务
    7.2 循环直到将这个任务执行完毕(剩余需执行时长为0)
        7.2.1 遍历所有时段，每个时段的结束时间所在位置指出了在其之前最近的可用的位置，检查这个位置是否在当前时段内，如果在，则占用此位置并合并至前一个等价类。如果不在，则检查下一个时段。
        7.2.2 若所有时段均检查完但并未成功调度，那么整个调度方案失败。若其中的某一个时段完成本轮单位时长的调度，则将之后每次单位时长的调度的结束时间改为该时段的结束时间。

7. 如何简洁快速地做两次询问？

8.2.1 两次询问
        8.2.1.1 第一次，询问当前任务若换到后面遍历到的某一个位置时，这个位置所在的时段是否处于当前任务的可执行时段中的某一个。也即，遍历当前任务的开始和结束时间，如果后面的这个位置处于当前的时段，则进行第二次询问
        8.2.2.2 第二次，询问后面位置的任务若换到当前位置，当前位置所处的时段是否处于后面的任务的可执行时段中的一个。方式同8.2.1.1

8. 前后端通信如何联调数据格式？

//数据格式
/**
 * [
 *  {
 *      name:'A',
 *      start:[-,2,7],
 *      end:[-,4,9],
 *      exeTime:2,
 *      weight:3
 *   },
 *  ...
 * ]
 */

9. 整体工作流程

1.用户填写数据，此时不需要整理时间堆和任务堆，交给算法模块整理
2.数据交送后端，接口转送算法模块，首先转换为实体类Task数组列表
3.在转化为实体数组的过程中，先对每个任务的开始结束时间做升序的堆排序
4.然后将时间堆排序后的任务列表做基数排序
 4.1 首先先对优先级做升序的桶排序
 4.2 然后对开始时间做降序的堆排序
这样任务列表按开始时间为第一优先级，优先级为第二优先级进行的排序
5.初始化结果数组，0索引弃用
6.初始化等价类数组，0索引弃用
7.根据任务列表做调度
    7.1 获取当前任务
    7.2 循环直到将这个任务执行完毕(剩余需执行时长为0)
        7.2.1 遍历所有时段，每个时段的结束时间所在位置指出了在其之前最近的可用的位置，检查这个位置是否在当前时段内，如果在，则占用此位置并合并至前一个等价类。如果不在，则检查下一个时段。
        7.2.2 若所有时段均检查完但并未成功调度，那么整个调度方案失败。若其中的某一个时段完成本轮单位时长的调度，则将之后每次单位时长的调度的结束时间改为该时段的结束时间。
8.遍历整个结果数组，将结果调整至优先级最优
    8.1 获取当前位置(可能有任务也可能没任务)
    8.2 循环查询当前位置后的所有位置
        8.2.1 两次询问
            8.2.1.1 第一次，询问当前任务若换到后面遍历到的某一个位置时，这个位置所在的时段是否处于当前任务的可执行时段中的某一个。也即，遍历当前任务的开始和结束时间，如果后面的这个位置处于当前的时段，则进行第二次询问
            8.2.2.2 第二次，询问后面位置的任务若换到当前位置，当前位置所处的时段是否处于后面的任务的可执行时段中的一个。方式同8.2.1.1
        8.2.2 一次比较
            8.2.2.1 若8.2.1的两次询问的结果时可以交换，那么比较优先级，如果后面任务的优先级较高，则交换；否则，不换
    这个循环过程持续到没有交换产生为止
9.结果数组由业务接口响应回前端
10.前端接收后，预处理结果数组，并回显

卸载

npm uninstall TaskScheduling

即将上线

1.并行时间最优方案