Days needed to finish recurring tasks

Clarify first. Task i runs on day 1 and then every intervals[i] days after that: days 1, 1 + k, 1 + 2k, ... with k = intervals[i]. Any number of tasks can finish on the same day. Return the smallest day d such that the total number of completions on days 1..d is at least goal. Confirm the convention for the first run (day 1, not day k), because it changes the count formula by one.

Count by a fixed day. By day d, task i has run (d - 1) // k + 1 times. So the total is

done(d) = sum((d - 1) // k_i + 1 for every i).

Brute force: walk the days. Start at day 1, add each task's completions for that day, and stop when the running total reaches goal. That is correct, but the answer can be as large as about 10^5 * 10^9 = 10^14 days (one task, interval 10^5, goal 10^9). Walking day by day is far too slow.

Key observation: done(d) is monotone. Each term never decreases as d grows, so done(d) >= goal is false for small d and true from some day on. That is the shape for binary search on the answer.

Bounds.

• Low: day 1. On day 1 every task runs once, so if goal <= n the answer is 1.
• High: the fastest task alone finishes goal runs by day (goal - 1) * min(intervals) + 1. The other tasks only help, so this day always works.

Invariant. Keep lo as a day that may still be the answer and hi as a day known to satisfy done(hi) >= goal. Test mid = (lo + hi) // 2. If it works, set hi = mid. If not, set lo = mid + 1. When lo == hi, it is the smallest working day.

Two speedups that matter in practice.

• Intervals are at most 10^5, so many repeat. Group equal intervals with a counter and multiply, which turns n terms into at most U distinct terms.
• Stop summing as soon as the total reaches goal. That keeps each check cheap and keeps the sum bounded (it matters in languages with fixed-width integers).

from collections import Counter


def tasks_done_by(day: int, groups: list[tuple[int, int]], goal: int) -> int:
    """Completions on days 1..day, capped once it reaches goal."""
    total = 0
    for interval, count in groups:
        total += ((day - 1) // interval + 1) * count
        if total >= goal:
            return total
    return total


def min_days(intervals: list[int], goal: int) -> int:
    """Smallest day by which at least `goal` task runs have finished."""
    if not intervals:
        raise ValueError("need at least one task")
    if goal <= 0:
        return 0
    groups = sorted(Counter(intervals).items())  # fast tasks first
    lo = 1
    hi = (goal - 1) * groups[0][0] + 1  # fastest task alone is enough
    while lo < hi:
        mid = (lo + hi) // 2
        if tasks_done_by(mid, groups, goal) >= goal:
            hi = mid
        else:
            lo = mid + 1
    return lo


def min_days_brute(intervals: list[int], goal: int) -> int:
    """Walk day by day. Only for small inputs and testing."""
    total, day = 0, 0
    while total < goal:
        day += 1
        total += sum(1 for k in intervals if (day - 1) % k == 0)
    return day


if __name__ == "__main__":
    assert min_days([1], 1) == 1
    assert min_days([3, 5], 2) == 1
    assert min_days([3, 5], 3) == 4
    assert min_days([3, 5], 5) == 7
    assert min_days([2, 2, 2], 7) == 5
    assert min_days([100_000], 10**9) == (10**9 - 1) * 100_000 + 1
    import random
    for _ in range(500):
        ivs = [random.randint(1, 8) for _ in range(random.randint(1, 5))]
        g = random.randint(1, 40)
        assert min_days(ivs, g) == min_days_brute(ivs, g), (ivs, g)
    print("ok")

• Grouping: O(n + U log U) time and O(U) space, where U <= min(n, 10^5) is the number of distinct intervals.
• Each feasibility check: O(U) time, often less because it stops at goal.
• Binary search: O(log(goal * min_interval)) checks, about 47 for the largest inputs.
• Total: O(n + U log(goal * min_interval)) time, O(U) extra space.
• Brute force: O(answer * n) time, which can be 10^14 * 10^5.

• intervals = [1], goal = 1 -> 1 (one run on day 1).
• intervals = [3, 5], goal = 2 -> 1 (both run on day 1).
• intervals = [3, 5], goal = 3 -> 4 (task 0 runs again on day 4).
• intervals = [3, 5], goal = 5 -> 7 (runs on days 1, 1, 4, 6, 7).
• intervals = [2, 2, 2], goal = 7 -> 5 (3 on day 1, 3 on day 3, the 7th on day 5).
• intervals = [4, 1], goal = 6 -> 5 (days 1..5 give 5 from the daily task, plus day 1 and day 5 from the other: 7 by day 5, 5 by day 4).
• goal <= len(intervals) -> 1.
• intervals = [100000], goal = 10^9 -> 99999999900001 (upper bound is exact; no overflow in Python).
• Randomized check against the day-by-day brute force on small inputs.

1. Tasks start on day k instead of day 1. The count becomes d // k, and the high bound becomes goal * min_interval. This is LeetCode's "minimum time to complete trips" shape. The binary search does not change.
2. Each task has its own start day s_i. Count max(0, (d - s_i) // k_i + 1). It is still monotone. Raise the high bound to max(s) + (goal - 1) * min_interval. Grouping by interval no longer works directly, so group by (s_i, k_i) pairs.
3. Daily capacity: at most c completions per day. Monotonicity still holds, but the count is no longer a closed form. Simulate with a heap of next run days and a queue of backlog, or note that the answer is at least ceil(goal / c) and check it with event sweeps.
4. Many goals queried against the same intervals. Run one binary search per query, O(q * U log(...)). For many queries, sort them and reuse search bounds, since a larger goal never has a smaller answer.
5. Tasks stop after m_i runs. Count min(m_i, (d - 1) // k_i + 1). Check first that the total of m_i reaches goal; if it does not, return -1.

Mid-level (L4)

• Writes the per-task count formula correctly and handles the day-1 convention.
• Sees that walking day by day is too slow and moves to binary search on the answer.
• Gets the loop bounds right (lo < hi, hi = mid) and returns the smallest day.

Senior (L5)

• States why done(d) is monotone and gives a tight, safe upper bound.
• Mentions the early exit in the check and overflow in fixed-width languages.
• Tests the edge cases unprompted: goal <= n, one task, the largest bound.

Staff (L6+)

• Groups equal intervals and explains when that helps.
• Adapts quickly to start offsets, run caps, and daily capacity, and says which ones break the closed form.
• Discusses how to serve many goal queries or a changing task set.