A command-line API for generating a schedule from a list of projects, accustomed to your habits.
To begin, our algorithm firstly breaks up the timeline from when the schedule is generated upto the final due-date across all projects into 15-minute intervals. We would begin by generating a 'naive' schedule that would push the work sessions as far back as possible. This is a rather simple algorithm that only involves a simple sorting of the tasks by due date, traversing them in reverse order, and assigning each interval directly preceding a due date of a project to working on that project until it is done. If the intervals directly preceding such due date are already full (working on a different project), it moves the pointer left until it reaches an empty interval with no current tasks. If at any point the current interval is in the past, it is impossible to create a schedule under any circumstance.
Next, we removed all intervals that corresponded to sleep times, meal times, and specific designated events, as well as intervals in the past and intervals in the far future (past all due dates). This would leave us with essentially a string of 1s and 0s, where each 1 represented a 15 minute interval of work, and each 0 represented a 15 minute break.
The hard part here comes in optimizing this schedule further, where we opted on attempting to minimize a cost that represented the sum of (Break/Session Time - Optimal Break and Session Time)^2, where each break/session time is represented by a consecutive substring of 0s or 1s within the full string. There was an observation we made that moving any of such 1s to the left would always return a valid schedule in every circumstance, which we used to our advantage.
In order to do this, we utilized a dynamic programming algorithm which initially ran at a bad time complexity, but was then further optimized to get rid of a nested loop using Convex Hull Trick to query the minimum point on a series of parabolas. This dynamic programming algorithm would essentially traverse the string in reverse, and simulate adding a series of substrings of 0s and 1s at a time. We essentially have a 3D dynamic programming array where dp[index][number of ones used so far][last digit used] memoizes the minimum cost possible at the current substring [index, length of string), containing a specific number of ones used so far, as well as the digit at index. To make sure that ones are never moved to the right, we keep track of a suffix array.
To actually fill in this table, the property dp[i][j][0] = dp[a][j][1] + (a-i-k)^2 was utilized, which essentially states that adding (a-i) zeroes to the left of the most optimal substring [a, length of string) where S[a] = 1 will increase the cost by (a-i-optimal break time)^2. The additional property dp[i][j][1] = dp[a][b][0] + (a-i-k)^2 was also utilized, which essentially states the same thing, but adding (a-i) ones instead where S[a] = 0. While we originally used a nested loop to iterate through all values of a from i to the length of the string, we realized that this would be incredibly inefficient, and opted to optimize it further using convex hull trick, by treating each index dp[a][j][1] as a parabola that had it’s vertex at y = dp[a][j][1] and x = (a-k). This would allow us to query and update each row of the dp table in O(N) time, without requiring a nested loop.
From there, we keep track of a separate array storing where that optimal parabola came from, and use backtracking to generate an optimized string of ones and zeroes which would then be utilized to store the most optimal 15 minute intervals of breaks and work periods.