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⁶ (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⁶
• 1 ≤ N ≤ 10⁶
• 0 ≤ M ≤ 10⁶
• 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⁶

Example 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

解法

关键约束：依赖 PID1 → PID2 表示 start[PID1] < start[PID2] 且 end[PID2] < end[PID1]。先按依赖图做拓扑：start 时间从小到大处理(child 的 start > parent 的 start)，end 时间从大到小处理(child 的 end < parent 的 end)。具体实现：把每个 PID 的 [S, E] 当作下界 / 上界初值；对依赖图做拓扑序，按拓扑顺序更新 start[u] = max(start[u], start[predecessor] + 1)；反拓扑序更新 end[u] = min(end[u], end[predecessor] - 1)。最后检查每个 start ≤ end，否则 IMPOSSIBLE。复杂度 O(N + M)。

from typing import List, Optional

class Scheduler:
    def __init__(self, processes: List[List[int]], dependencies: List[List[int]]):
        n = len(processes)
        self.n = n
        self.start = [0] + [p[0] for p in processes]
        self.end = [0] + [p[1] for p in processes]
        self.children = [[] for _ in range(n + 1)]
        self.indeg = [0] * (n + 1)
        for u, v in dependencies:
            self.children[u].append(v)
            self.indeg[v] += 1
        self.deps = dependencies

    def print_schedule(self) -> str:
        from collections import deque
        order = []
        q = deque([i for i in range(1, self.n + 1) if self.indeg[i] == 0])
        indeg = self.indeg[:]
        while q:
            u = q.popleft()
            order.append(u)
            for v in self.children[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        if len(order) != self.n:
            return "IMPOSSIBLE"
        for u in order:
            for v in self.children[u]:
                if self.start[v] < self.start[u] + 1:
                    self.start[v] = self.start[u] + 1
        for u in reversed(order):
            for v in self.children[u]:
                if self.end[u] > self.end[v] - 1:
                    self.end[u] = self.end[v] - 1
        lines = []
        for i in range(1, self.n + 1):
            if self.start[i] > self.end[i]:
                return "IMPOSSIBLE"
            lines.append(f"{self.start[i]} {self.end[i]}")
        return "\n".join(lines)

A supermarket has many customers entering and exiting at various points. They want to keep track of customers and get notification when a customer leaves the store. There are number of checkout lines, where customers with basket of items queue to pay and exit the store. Individual checkout lines and customers are assigned numerical IDs. As happens in life, sometimes customers want to add more items to their baskets and sometimes they realise that they don't need certain items they picked up earlier and remove them from the basket. To enforce checkout priorities a few rules have been implemented in the supermarket: A customer cannot switch the lines before exit once they join a given checkout line. If a customer increases their items to purchase, they must go to the back of the same line. If a customer removes items from their basket, they will keep their position in the line (or leave the store if they don't have any more items). A customer will leave the supermarket as soon as they have no items left to checkout. Note that the lines with smaller IDs are closer to the exit, so if two customers pass the checkout line at the same time, the one closer to the exit would leave the store first. Problem Statement You will receive the stream of N instructions. Each instruction can be one of the following actions: CustomerEnter - indicates that a customer joined a checkout line. Attributes: CustomerId, LineNumber and NumItems. BasketChange - indicates that a customer changed number of items in their basket. Attributes: CustomerId and NewNumItems. LineService - indicates that several items have been processed in the line. Attributes: LineNumber and NumProcessedItems. LineService - indicates that 1 item has been processed in every line (if there are k lines then in total k items are processed). Explanation There are 2 customers (123 and 2) queued on two lines (1 and 2). When first LineService is called on both lines, both queued customers still have some items to check out. Namely, customer 123 has still 4 items, and customer 2 has 2 items to checkout. Then customer 3 joins to the 1st line. After next LineService on the 1st line, both customers with 123 and 3 IDs are checked out (first 123, and then 3). Customer 2 is still in the line.

Constraints

N/A

Example 1

Input:

instructions = ["CustomerEnter 123 1 5", "CustomerEnter 3 1 2", "LineService 1 4", "BasketChange 123 6", "LineService 1 5"]

Output:

[3, 123]

Explanation: Upon first LineService 4 out of 5 items of customer 123 are processed. However, customer then increases the number of items in their basket (namely adds 1 extra item), this puts them at the back of the line. During the next LineService call customer 3 is checked out first, and customer 123 is checked out next (as they only had 2 items left to process).

解法

每条 line 用 deque 维护排队 customer。CustomerEnter push 到对应 line 末尾。BasketChange：若新数量 < 当前数量 → 仅更新(保持位置)；否则把该 customer 从队中删除再插入到末尾(更新数量)。LineService line k：从队首扣减 items，扣完后弹出 customer 并记录出场顺序；同时间步内 line ID 小的先出场(同 LineService 内已天然有序)。复杂度均摊 O(N)，删除中间用懒删除或链表。

from typing import List
from collections import deque, OrderedDict

def customer_checkout(instructions: List[str]) -> List[int]:
    lines = {}
    customer_line = {}
    customer_items = {}
    exits = []
    for ins in instructions:
        parts = ins.split()
        cmd = parts[0]
        if cmd == "CustomerEnter":
            cid, ln, n_items = int(parts[1]), int(parts[2]), int(parts[3])
            lines.setdefault(ln, OrderedDict())[cid] = True
            customer_line[cid] = ln
            customer_items[cid] = n_items
        elif cmd == "BasketChange":
            cid, new_n = int(parts[1]), int(parts[2])
            ln = customer_line[cid]
            if new_n > customer_items[cid]:
                del lines[ln][cid]
                lines[ln][cid] = True
            customer_items[cid] = new_n
            if new_n == 0:
                del lines[ln][cid]
                exits.append(cid)
                del customer_line[cid]
        elif cmd == "LineService":
            if len(parts) == 3:
                ln, k = int(parts[1]), int(parts[2])
                q = lines.get(ln)
                if not q: continue
                while k > 0 and q:
                    cid = next(iter(q))
                    take = min(customer_items[cid], k)
                    customer_items[cid] -= take
                    k -= take
                    if customer_items[cid] == 0:
                        del q[cid]
                        exits.append(cid)
                        del customer_line[cid]
            else:
                for ln in sorted(lines.keys()):
                    q = lines[ln]
                    if not q: continue
                    cid = next(iter(q))
                    customer_items[cid] -= 1
                    if customer_items[cid] == 0:
                        del q[cid]
                        exits.append(cid)
                        del customer_line[cid]
    return exits

Write a function daysBetween that returns the number of days between two calendar dates. Each date is represented by three integers: year, month, and day. The first date is guaranteed to occur before the second date. Do not use system-provided date objects or built-in date-difference helpers. Compute the answer directly from the date components. Function Description Complete the function daysBetween in the editor below. daysBetween has the following parameters:

• int year1: the year of the first date
• int month1: the month of the first date
• int day1: the day of the first date
• int year2: the year of the second date
• int month2: the month of the second date
• int day2: the day of the second date Returns int: the number of days between the two dates

Constraints

• 1 ≤ month1, month2 ≤ 12
• Both input dates are valid calendar dates.
• The first date always occurs before the second date.
• Do not use built-in date libraries or system date objects.

Example 1

Input:

year1 = 2010
month1 = 5
day1 = 1
year2 = 2011
month2 = 5
day2 = 1

Output:

365

Explanation: From 2010-05-01 to 2011-05-01 there are 365 days.

Example 2

Input:

year1 = 2020
month1 = 2
day1 = 27
year2 = 2020
month2 = 3
day2 = 1

Output:

3

Explanation: The interval crosses leap day in 2020: Feb 27 -> Feb 28 -> Feb 29 -> Mar 1, so the difference is 3 days.

Example 3

Input:

year1 = 2019
month1 = 12
day1 = 31
year2 = 2020
month2 = 1
day2 = 1

Output:

1

Explanation: The dates are consecutive calendar days across a year boundary.

解法

把两个日期分别转换成 "从公元 0 年 1 月 1 日起的天数"，再相减取绝对值。日期天数计算公式：累加完整年份天数(每 4 年闰 1 天，每 100 年不闰，每 400 年再闰)+ 当年完整月份天数 + 当月日数。复杂度 O(1)。

def days_between(year1: int, month1: int, day1: int,
                  year2: int, month2: int, day2: int) -> int:
    def is_leap(y):
        return y % 4 == 0 and (y % 100 != 0 or y % 400 == 0)
    months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    def to_days(y, m, d):
        days = 0
        for yy in range(1, y):
            days += 366 if is_leap(yy) else 365
        for mm in range(1, m):
            days += months[mm - 1]
            if mm == 2 and is_leap(y):
                days += 1
        days += d - 1
        return days
    return abs(to_days(year2, month2, day2) - to_days(year1, month1, day1))

class Solution {
    int daysBetween(int year1, int month1, int day1, int year2, int month2, int day2) {
        return Math.abs(toDays(year2, month2, day2) - toDays(year1, month1, day1));
    }
    private int toDays(int y, int m, int d) {
        int[] months = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int days = 0;
        for (int yy = 1; yy < y; yy++) days += isLeap(yy) ? 366 : 365;
        for (int mm = 1; mm < m; mm++) {
            days += months[mm - 1];
            if (mm == 2 && isLeap(y)) days++;
        }
        return days + d - 1;
    }
    private boolean isLeap(int y) { return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0); }
}

class Solution {
public:
    int daysBetween(int year1, int month1, int day1, int year2, int month2, int day2) {
        return abs(toDays(year2, month2, day2) - toDays(year1, month1, day1));
    }
private:
    int toDays(int y, int m, int d) {
        int months[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int days = 0;
        for (int yy = 1; yy < y; yy++) days += isLeap(yy) ? 366 : 365;
        for (int mm = 1; mm < m; mm++) {
            days += months[mm - 1];
            if (mm == 2 && isLeap(y)) days++;
        }
        return days + d - 1;
    }
    bool isLeap(int y) { return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0); }
};