The article will calculate the optimal read list for a given number of days.

Problem Statement

You have been given the number of chapters a person wants to read and the days he has to read all the chapters. You need to calculate the optimized solution of chapters so that the person doesn't read too many chapters in a single day.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Example

Input

pages = {3, 2, 2, 4}
days = 3

Output

Day 1: 1
Day 2: 2 3
Day 3: 4

Explanation

In the given input graph, all the possible paths will be:

{1,2}, {3}, {4} -> 5

{1}, {2,3}, {4} -> 4

{1}, {3}, {2,4} -> 6

{2}, {1,3}, {4} -> 5

{2}, {3}, {1,4} -> 7

{1}, {2}, {3,4} -> 6

The most optimal read will be {1}, {2,3}, {4}. The maximum number of pages to read in a single day will be 4.

Algorithm

With the help of DFS Algorithm, we will solve this problem. We start from chapter 1 and apply DFS to count the edges. We will keep an eye on the visited vertex. If we reach the destination vertex and the sum of reaching the destination is less than the optimal path, then we update the optimal path to this path. We will construct a directed acyclic graph and then find the optimal path using DFS, as mentioned above.

Let's start with the implementation of the code.

C++ Code

/* C++ Program: Optimal read list for given number of days */
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <cmath>
#include <limits>
using namespace std;
/* print the reading schedule to follow */
void printReadingSchedule(const vector<int>& pages, int nDays) {
int nChapters = pages.size();
if (nChapters < nDays) {
cout << "read a chapter per day." << endl;
return;
}
if (nDays == 0) {
cout << "no day to read." << endl;
return;
}
/* store optimal costs, each cost means the sum of abs(deviation)s */
int dp[nDays + 1][nChapters + 1];
/* for constructing path */
int prev[nDays + 1][nChapters + 1];
memset(prev, -1, sizeof(prev));
/* accumulate sum */
int sum[nChapters + 1];
sum[0] = 0;
for (int i = 1; i <= nChapters; ++i) {
sum[i] = sum[i - 1] + pages[i - 1];
}
int avg = round(sum[nChapters]/(double)nDays);
/* read all chapters in one day */
for (int j = 1; j <= nChapters; ++j) {
dp[1][j] = abs(sum[j] - avg);
}
for (int i = 2; i <= nDays; ++i) {
for (int j = 2; j <= nChapters; ++j) {
if (i == j) {
/* if number of days equals to chapters, read a chapter per day */
dp[i][j] = dp[i - 1][j - 1] + abs(sum[j] - sum[j - 1] - avg);
prev[i][j] = j - 1;
} else {
dp[i][j] = numeric_limits<int>::max();
for (int k = i - 1; k < j; ++k) {
int rangeSum = sum[j] - sum[k];
int cost = dp[i - 1][k] + abs(rangeSum - avg);
if (cost < dp[i][j]) {
dp[i][j] = cost;
prev[i][j] = k;
}
}
}
}
}
/* construct path */
list<int> path;
{
int i = nDays;
int j = nChapters;
while (prev[i][j] != -1) {
int k = prev[i][j];
path.push_front(k);
i--;
j = k;
}
path.push_back(nChapters);
}
/* print */
int day = 1;
int s = 0;
for (auto e : path) {
printf("Day %d: ", day);
while (s < e) {
printf("%d ", s + 1);
++s;
}
printf("\n");
++day;
}
}
/* Main Program */
int main() {
printReadingSchedule({3, 2, 2, 4}, 3);
return 0;
}

Input

pages = {3, 2, 2, 4}
days = 3

Output

Day 1: 1
Day 2: 2 3
Day 3: 4

Complexities

Time complexity

O(NxM), where N stands for the pages and M stands for the days available.

Reason: We are traversing all the possible outcomes after calculating the average of the pages in the chapters. So, we can conclude that the time complexity of this algorithm is O(NxM).

Space complexity

O(NxM), where N stands for the pages and M stands for the days available

Reason: We need a matrix of size NxM to save path count from keeping track of the movement of the graph. Check out this problem - Subarray Sum Divisible By K

Frequently Asked Questions

What do you understand by the depth of a vertex?

The number of branches that lead from a root to a vertex determines the vertex's depth. Therefore, the root's depth is zero. The number of the vertex in the path from the root to the vertex determines the vertex's level.

Why does DFS employ stack?

When a dead end occurs during any iteration, the Depth First Search (DFS) method employs a stack to track where to find the next vertex to begin a search.

What do you mean by a simple path in a graph?

A simple path in geometry is a simple curve, precisely a continuous injective function from an actual number interval to a metric space, topological space, or, more generally. A simple path in graph theory is a path through a graph that doesn't have recurring vertices.

What is the load factor of a hash table?

The load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased, and n is the overall size of the hash table.

What memory representation does a graph have?

A graph can be kept in memory in three ways: Edges act as pointers, and nodes as objects. A matrix that includes each edge weight that connects nodes x and y. edges between numbered nodes, listed.

Conclusion

In the article, we have calculated the optimal read list for a given number of days. We hope this article will help you understand the concept of graphs. Check out our other blogs on this topic: