Feature #3: Identify Peak Interaction Times

Description

For this next Twitter feature, the company has decided to create an API that can be used by business accounts on Twitter. This API will identify three disjoint time intervals in which the most users followed or interacted with the businesses’ Tweets. You will be given the historical data of user interaction per hour for a particular business’ Twitter account. The API will have another parameter for hours. Your goal is to find three continuous intervals of a size equal to hours such that the sum of all the entries is the greatest. These time intervals should not overlap with each other.

Consider a Twitter profile with the following history of user interactions: {0, 2, 1, 3, 1, 7, 11, 5, 5} and hours = 2. The interaction array represents that this particular business’ account received no interactions during the first hour, 2 in the second hour, and so on. In this case, we want three intervals of size 2 with the maximum sum. These intervals will be {1, 3}, {7, 11}, and {5, 5}. Your function should return the indices of the first elements in the intervals. Therefore, the output will be: {2, 5, 7}.

Note: If there are multiple answers, you need to return the chronologically earliest one.

Solution

To solve this problem, we can start by calculating the sum of n intervals for each index, where n = hours. We can store these sums in an array called sums. Then, all that’s left will be to find the lexicographically smallest tuple of indices {a, b, c} that maximizes sums[a] + sums[b] + sums[c].

Let’s take a look at the algorithm to ...