Simulate Modulo-Assigned Document Indexers with Wrap-Around and Rank the Busiest

Documents are indexed through a processing queue served by m indexers, numbered 0 to m - 1. Document i (0-based) arrives at time queue_time[i] and needs processing_time[i] time units. It goes to indexer i mod m if that indexer is not busy. Otherwise it goes to the next indexer that is not busy, trying i mod m + 1, i mod m + 2, and so on, wrapping around from m - 1 to 0. If every indexer is busy, the document is dropped.

• Step 1: report the total number of documents processed successfully, and the indexer that processed the most documents.
• Step 2: report the top k indexers and the share of the processed documents that they handled.

Function Signature

def index_documents(m: int, queue_time: list[int], processing_time: list[int], k: int) -> tuple[int, int, list[int], int]:

Return the tuple (processed, busiest, top_k, top_k_count).

Rules

• Documents are handled in index order, and queue_time is non-decreasing.
• An indexer that starts a document at time s with processing time p is busy during [s, s + p) and free again from time s + p onward. A document that arrives exactly at s + p can be assigned to it. The original problem does not settle this boundary; this version fixes it.
• A document arriving at time t tries indexers in the order i mod m, (i mod m) + 1, ..., wrapping to 0 after m - 1, and is assigned to the first one that is free at time t. If all m indexers are busy, the document is dropped and counts for no one.
• processed is the number of documents that were assigned.
• Rank the indexers by the number of documents they processed, most first, and break ties by the smaller indexer id. Indexers that processed nothing still take part in the ranking. busiest is the first indexer in this ranking, and top_k lists the first k, in ranking order.
• top_k_count is the total number of documents processed by the indexers in top_k. The share asked for in Step 2 is top_k_count / processed. It is returned as a count so that the answer is exact.

Constraints

• 1 <= m <= 10^5
• 1 <= n <= 10^5, where n = len(queue_time) == len(processing_time)
• 0 <= queue_time[i] <= 10^9, and queue_time is non-decreasing
• 1 <= processing_time[i] <= 10^9, so every finish time is at most 2 * 10^9 and fits in a 32-bit signed integer
• 1 <= k <= m

Examples

Example 1

Input: m = 3, queue_time = [1, 2, 3, 7], processing_time = [5, 4, 3, 2], k = 2
Output: (4, 0, [0, 1], 3)

Documents 0, 1 and 2 go to indexers 0, 1 and 2, which are all busy until time 6. Document 3 arrives at time 7. 3 mod 3 = 0, and indexer 0 is free again, so it takes the document. The counts are [2, 1, 1]: all 4 documents are processed and indexer 0 is the busiest. Indexers 1 and 2 tie, so the smaller id goes into the top 2. The top 2 handled 3 of the 4 documents, a 75% share.

Example 2

Input: m = 3, queue_time = [0, 0, 0, 1, 2, 5], processing_time = [1, 9, 9, 4, 3, 2], k = 2
Output: (5, 0, [0, 1], 4)

• Documents 0, 1 and 2 go to indexers 0, 1 and 2. Indexer 0 is busy until time 1, and indexers 1 and 2 until time 9.
• Document 3 arrives at time 1. Indexer 0 is free from time 1, so it takes the document and is busy until 5.
• Document 4 arrives at time 2. Indexers 1, 2 and 0 are all busy, so the document is dropped.
• Document 5 arrives at time 5. Indexer 2 is busy, so it wraps around to indexer 0, which is free from time 5.

The counts are [3, 1, 1], and 5 documents are processed. The top 2 handled 4 of them, an 80% share.

Example 3

Input: m = 1, queue_time = [0, 1], processing_time = [2, 1], k = 1
Output: (1, 0, [0], 1)

The single indexer is still busy when document 1 arrives, so document 1 is dropped.