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.

Wraparound Document Indexers: Processed Count, Busiest Indexer and Top-K Share

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.

Answer two questions about the run:

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

Implement index_documents(m, queue_time, processing_time, k) and return (processed, busiest, top_k, top_k_count).

Rules

• Documents are handled in index order (0, 1, 2, ...), and queue_time is non-decreasing, so several documents can share an arrival time.
• 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.
• 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, starting there 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 all m 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 indexers, 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.

Return value per language

• Python: the tuple (processed, busiest, top_k, top_k_count), with top_k a list.
• JavaScript: the array [processed, busiest, top_k, top_k_count].
• Java: a java.util.List<Object> holding processed, busiest, top_k (a java.util.List<Integer>) and top_k_count, in that order.
• C++: a std::tuple<int, int, std::vector<int>, int>.

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

No input value, finish time or returned count exceeds 2^31 - 1, so 32-bit int suffices in Java and C++.

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.

Hints

1. The first indexer tried by document i is always i mod m, however many earlier documents were dropped.
2. An indexer whose document finishes at s + p can take a document arriving at exactly s + p, but not one arriving at s + p - 1.
3. Every indexer, including one that processed nothing, is part of the ranking, and equal counts are ordered by the smaller id.

Approach

Simulate the documents in index order with two min-heaps. busy holds (finish_time, indexer) for every indexer that is currently working. Before document i (arriving at t) is placed, every entry with finish_time <= t is popped, because an indexer is free from s + p onward; each released indexer j is pushed into the free heap under the key i + ((j - i) mod m). Initially the free heap holds the keys 0, 1, ..., m - 1.

Invariant: while document i is handled, every free key lies in [i, i + m - 1], maps to indexer key mod m, and key - i is that indexer's probe distance from i mod m. Keys pushed at step i' lie in [i', i' + m - 1]; the keys are distinct because each indexer is free at most once; and popping the minimum at every step where the heap is non-empty leaves all remaining keys at least i + 1. Therefore the smallest free key is exactly the first free indexer in the order i mod m, i mod m + 1, ... with wraparound. If the free heap is empty, all m indexers are busy and the document is dropped without changing any count, but the next document still starts from (i + 1) mod m.

After the simulation, all m indexers are sorted by (-count, id): busiest is the first, top_k is the first k, and top_k_count sums only those k counts. Each document costs O(log m) amortized heap work, because every assigned document is released at most once.

Edge cases: m = 1 (every overlapping document is dropped); several documents with one arrival time (handled in index order, and a document started at t is never released at t because p >= 1); an arrival exactly at s + p (free) versus s + p - 1 (busy); drops that still advance the start index; and k larger than the number of indexers that did any work, where zero-count indexers fill the tail of the ranking in id order.

• Time complexity: O((n + m) log m)
• Space complexity: O(m)