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.
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;
}
You can also try this code with Online C++ Compiler
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:
245+ registered 
