Quick Overview

Given the reading time available on each day and the time each chapter of a book takes, find the fewest days needed to read every chapter in order when a chapter can never be split across days, or report that the book cannot be finished. It tests simulation with per-day capacity, ordering constraints, and impossible cases.

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

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Online Assessment

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 ```python 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.

Overview: Given the reading time available on each day and the time each chapter of a book takes, find the fewest days needed to read every chapter in order when a chapter can never be split across days, or report that the book cannot be finished. It tests simulation with per-day capacity, ordering constraints, and impossible cases.

Read the full Software Engineer interview experience this question came from

You want to read every chapter of a book, and you have a list of days to do it in. The array `time` describes the days: 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. You may read more than one chapter on the same day 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. Implement `days_to_finish(time, book)`. ### 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` - The result is always in the range `-1` to `len(time)`, and no amount of time you need to track exceeds `10000` within a day, so 32-bit integers are sufficient in every language. ### 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.

Constraints

  • 1 <= len(time) <= 100000
  • 0 <= len(book) <= 100000
  • 0 <= time[i] <= 10000
  • 1 <= book[j] <= 10000
  • Chapters must be read in order, a chapter cannot be split across days, and unused time does not carry over to the next day
  • The answer lies in [-1, len(time)] and every per-day quantity is at most 10000, so 32-bit integers suffice

Examples

Input: ([3, 5, 2, 6], [2, 2, 3, 4])

Expected Output: 4

Input: ([4, 4], [5])

Expected Output: -1

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.

Loading coding console...

Show the approach

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)