Fewest Days to Read a Book When Chapters Cannot Be Split Across Days

You want to read every chapter of a book. The array time describes the days available to you: day i gives you time[i] units of reading time. The array book describes the chapters: chapter j takes book[j] units of time to read.

On any day you may read more than one chapter if you have enough time, but every chapter must be read completely within a single day; a chapter can never be split across days. Return the number of days needed to finish the whole book, or -1 if the book cannot be finished within the given days.

Function Signature

def days_to_finish(time: list[int], book: list[int]) -> int:

Rules

• Chapters are read in order: chapter j + 1 can be started only after chapter j has been finished.
• Days are used in order starting from day 0. You may read nothing on a day.
• Reading time does not carry over: time left unused at the end of a day is lost.
• The answer is the smallest d such that the whole book can be read using only days 0 through d - 1 under these rules. If no such d <= len(time) exists, return -1.
• An empty book needs 0 days.

Constraints

• 1 <= len(time) <= 100000
• 0 <= len(book) <= 100000
• 0 <= time[i] <= 10000
• 1 <= book[j] <= 10000

Examples

Example 1

• Input: time = [3, 5, 2, 6], book = [2, 2, 3, 4]
• Output: 4
• Explanation: Day 0 has 3 units: chapter 0 (2 units) fits, but adding chapter 1 would need 4. Day 1 has 5 units: chapters 1 and 2 need exactly 5. Day 2 has 2 units, too few for chapter 3 (4 units). Day 3 has 6 units, and chapter 3 is finished. The book is finished using days 0 through 3, so 4 days are needed, and it cannot be done in fewer.

Example 2

• Input: time = [4, 4], book = [5]
• Output: -1
• Explanation: The only chapter needs 5 units, but no day offers more than 4, and a chapter cannot be split.

Example 3

• Input: time = [10, 1], book = [3, 3, 4]
• Output: 1
• Explanation: All three chapters need 10 units in total, which fits on day 0.

Finish the Book Day by Day

Hints

1. Reading a chapter on an earlier day never makes the rest of the schedule harder. What does that suggest about how much to read on each day?
2. Keep an index to the next unread chapter. For each day, start with that day's time and keep taking chapters while the next one still fits in what is left.
3. The total amount of time is not enough to decide the answer, because leftover minutes are lost at the end of each day. Stop the moment the index passes the last chapter, and handle the empty book before you start.

Approach

The reference walks the days in order and keeps a pointer j to the first unread chapter. On day i it starts with remaining = time[i] and repeatedly reads chapter j while book[j] <= remaining, subtracting its length and advancing j. As soon as j reaches len(book), days 0 through i were enough, so it returns i + 1. If every day is used and chapters remain, it returns -1; an empty book returns 0 immediately.

Why greedy is optimal: compare any valid schedule with the greedy one. By induction on the day, after each day the greedy pointer is at least as far as the other schedule's, because the greedy starts that day no further behind and packs chapters in order until the next one no longer fits, while the other schedule can read at most the same prefix of the remaining chapters in the same amount of time. So if any schedule finishes by day d - 1, the greedy does too, and the first day on which the greedy finishes is the smallest possible d. Leftover time is discarded at the end of each day, which is why comparing total time with the total length of the book is not a valid shortcut.

• Time complexity: O(len(time) + len(book))
• Space complexity: O(1)