FastPrepFastPrep
Problem Brief

Print Schedule

OA

We have a huge trading system at Optiver, running 20,000+ instances of binaries in production performing various functions. Processes often have dependencies on other processes to input data from various sources and fetch parameters configured in files and databases. Every week we need to start all these processes and also stop them in the correct order. The longer these processes run, the more money we make, so we want to schedule them to run for as long as possible. Scheduling these processes to run correctly and at the correct time is a complex task, which we want you to solve for us.

In this problem, you will be given a list of processes, each with a unique ID PID, a start time S - which is the earliest the process can start, and an end time E - which is the latest the process can end. You will also be given a list of inter-process dependencies, PID1 -> PID2, indicating that PID1 must start strictly before PID2 can start, and PID2 must end strictly before PID1 can end. Time for the week is divided into integer time units that start from 1 and go up to 10^6 (inclusive). The scheduler can only schedule processes to start or stop at the start of a time unit, for example at 1, 2, 1000, 999999 but not at 1.5, 700.1, etc.

Class Description

Your task is to implement the Scheduler class which has a constructor and a PrintSchedule method. The class constructor has the following parameters:

  • processes[0, ..., N-1]: an array of start-time and end-time pairs
  • dependencies[0, ..., M-1]: an array of pid1 and pid2 pairs

The PrintSchedule method does not take any parameters.

PrintSchedule should output the final schedule as N lines, one for each process in ascending order of PID. Each line i (where 1 ≤ i ≤ N) should contain two integers: S, E - the time at which the ith process (i.e., the process that has PID = i) starts and the time at which it ends respectively.

In the case where a correct schedule is not possible, just output "IMPOSSIBLE" instead of outputting the N lines.

Note: in a correct schedule, every process is able to run for at least one time unit.

Constraints

  • 1 ≤ S ≤ E ≤ 10^6
  • 1 ≤ N ≤ 10^6
  • 0 ≤ M ≤ 10^6
  • 1 ≤ PID1, PID2 ≤ N, and PID1 != PID2
  • All ordered pairs of PID1, PID2 are unique
  • Sum of N, M across all test cases does not exceed 10^6

1Example 1

Input
processes = [[1, 2], [100, 2100], [110, 2200], [200, 2330]], dependencies = [[1, 2], [3, 2]]
Output
"100 2100\n201 2099\n200 2330"
Explanation

Sample Output

100 2100
201 2099
200 2330 

class Scheduler {
    // write your code here for the Scheduler class
    constructor(processes, dependencies) {
        // constructor implementation
    }

    printSchedule() {
        // PrintSchedule method implementation
    }
}
Input

processes

[[1, 2], [100, 2100], [110, 2200], [200, 2330]]

dependencies

[[1, 2], [3, 2]]

Output

"100 2100\n201 2099\n200 2330"

Sign in to submit your solution.