Most booked day · Coding Gym

Solutions

This problem is not particularly difficult, but it does require combining a few key ideas. One of the main challenges depends on the programming language used, since date manipulation is involved. While all mainstream languages provide adequate tools to handle dates, practical difficulties may still arise.

At the time of writing, the latest C++ compiler available on HackerRank is outdated and does not support some of the more recent additions to std::chrono. As a result, solving this problem in C++ requires extra care and more manual handling of dates. For this reason, the C++ solutions are presented at the bottom of this page, as they are slightly more involved compared to those in other languages.

We have encountered a similar problem already at Coding Gym: “The lucky employee”. The core idea is the same, but instead of integer ranges, we now deal with date intervals.

The approach to tackle these two problems is called sweep line, a general technique used to solve problems involving intervals, ranges, or events over an ordered domain (such as time, coordinates, or dates). The idea is to transform each interval into a set of discrete events (such as a start and an end), sort these events, and then scan them in order while maintaining a running state.

As the sweep line “moves” from left to right across the domain, it updates a counter or data structure to reflect how many intervals are currently active. This makes it possible to efficiently compute quantities such as the maximum number of overlapping intervals, the total covered length, or the first point where a given condition is met.

However, the sorting part is not really necessary in our case as we’ll see in a moment.

Consider the following ranges:

The most frequent value can be computed efficiently using a difference array:

the start of each range contributes \(+1\) to the counter at that position
the end of each range contributes \(-1\) to the counter of the next position

Applying this rule gives:

1
2


0  1  2  3  4  5  6  7  8  9  10
0  2  1  0  -1 -1 -1 0  1  0  -1

The actual frequencies are obtained by computing the prefix sum of this array:

1
2


0  1  2  3  4  5  6  7  8  9  10
0  2  3  3  2  1  0  0  1  1  0

At this point, solving the problem reduces to finding the maximum value in the prefix sum array.

The same pattern applies to this challenge as well. The only difference is that instead of numeric indices, we are working with date spans. Therefore, the key step is to map each date to a numeric index, allowing us to track frequencies using the same prefix sum technique.

A convenient index to use is the number of days elapsed since the minimum possible date. According to the problem constraints, 2018-01-01 is the earliest date, so it can safely be used as the reference point (index 0).

Likewise, the maximum possible date is 2020-12-31, which allows us to determine the required size of the frequency array. The array length should be the number of days between the minimum and maximum dates plus 2: one extra position is needed because the date ranges are inclusive; another extra position ensures that the decrement applied to the last possible date does not go out of bounds.

With this mapping, each date can be converted into an integer index, and the solution can be applied exactly as in the integer-range case. This is the code in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


def solve(reservations):
    min_date = datetime(2018, 1, 1)
    max_date = datetime(2020, 12, 31)
    total_days = (max_date - min_date).days + 2
    
    freqs = [0] * total_days
    
    for reservation in reservations:
        start_idx = (datetime.strptime(reservation[0], "%Y-%m-%d") - min_date).days
        end_idx = (datetime.strptime(reservation[-1], "%Y-%m-%d") - min_date).days
        freqs[start_idx] += 1
        freqs[end_idx + 1] -= 1
    
    cumsum = list(accumulate(freqs))
    max_idx = cumsum.index(max(cumsum))
    
    result_date = min_date + timedelta(days=max_idx)
    return result_date.strftime("%Y-%m-%d")

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        reservations = []

        for _ in range(n):
            reservations.append(input().rstrip().split())

        result = solve(reservations)

        fptr.write(result + '\n')

    fptr.close()

Here is a similar idea in C#:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


class Solution {

    static string solve(List<List<string>> reservations)
    {
        var minDate = new DateTime(2018, 1, 1);
        int totalDays = (new DateTime(2020, 12, 31) - minDate).Days + 2;

        var freqs = Enumerable.Repeat(0, totalDays).ToArray();

        reservations.ForEach(r =>
        {
            freqs[(DateTime.Parse(r.First()) - minDate).Days]++;
            freqs[(DateTime.Parse(r.Last()) - minDate).Days + 1]--;
        });

        int runningSum = 0;
        var cumsum = freqs.Select(x => runningSum += x).ToArray();

        return minDate.AddDays(cumsum.ToList().IndexOf(cumsum.Max())).ToString("yyyy-MM-dd");
    }

    static void Main(string[] args) 
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine().Trim());

        for (int tItr = 0; tItr < t; tItr++) 
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());

            List<List<string>> reservations = new List<List<string>>();

            for (int i = 0; i < n; i++) 
            {
                reservations.Add(Console.ReadLine().TrimEnd().Split(' ').ToList());
            }

            string result = solve(reservations);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

This solution is linear in time (\(O(N + D)\), where \(N\) is the number of reservations and \(D\) is the number of days in the date range, that is actually constant here). It is the fastest and most efficient solution when the domain is small and contiguous.

Sparse domain

If the domain is very large or sparse (for example, if the date intervals are far apart or unbounded), an array-based approach may no longer be practical as we can’t exploit this constraint (=opportunity) anymore. In such cases, we can replace the array with a sorted map that stores only the dates where frequency changes occur, or sort a list later (we’ll see this approach afterwards).

Although dates are represented as strings, we still need to treat them as actual dates in order to compute the day immediately following the end of each reservation. For this reason, we temporarily convert date strings to datetime objects when computing the next day.

As before, we accumulate +1 at the start date and -1 at the day after the end date. The most popular day is then found by computing the prefix sum over the dates in chronological order. In Python, defaultdict(int) is convenient because it automatically initializes missing keys to 0. The final iteration explicitly uses sorted() to ensure dates are processed in order:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


def get_next_day(date_str):
    date = datetime.strptime(date_str, "%Y-%m-%d")
    return (date + timedelta(days=1)).strftime("%Y-%m-%d")

def solve(reservations):
    freqs = defaultdict(int)
    
    for reservation in reservations:
        freqs[reservation[0]] += 1
        freqs[get_next_day(reservation[-1])] -= 1
    
    max_count = 0
    running_sum = 0
    best = None
    
    for date in sorted(freqs.keys()):
        running_sum += freqs[date]
        if running_sum > max_count:
            max_count = running_sum
            best = date
    
    return best

The time complexity here is \(O(N log N)\) due to sorting the dates. It uses less memory for sparse or large domains, but is slower because of map operations and sorting.

Alternatively, we convert each reservation interval into two pairs: one increases the active count, and the other decreases it. All pairs are stored in a list and then sorted chronologically. By scanning the pairs in order and maintaining a running count of active reservations, we can track the maximum overlap and record the earliest date at which it occurs. In the sweep line approach described earlier, each pair is actually called event. Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


def solve(reservations):
    events = []
    
    for reservation in reservations:
        start = datetime.strptime(reservation[0], "%Y-%m-%d")
        end = datetime.strptime(reservation[-1], "%Y-%m-%d") + timedelta(days=1)
        events.append((start, 1))
        events.append((end, -1))
    
    events.sort()
    
    max_count = 0
    current_count = 0
    best_date = None
    
    for date, delta in events:
        current_count += delta
        if current_count > max_count:
            max_count = current_count
            best_date = date.strftime("%Y-%m-%d")
    
    return best_date

The complexity in this case is still \(O(N log N)\) due to sorting.

C++ Solutions

As anticipated, the C++ compiler currently available on HackerRank does not support the latest C++20 additions to std::chrono. Because of this limitation, writing a clean and idiomatic C++ solution becomes more challenging, especially when compared to other languages.

To illustrate the intended approach, the following implementation shows how the solution would look using the modern std::chrono facilities. This version closely mirrors the array-based strategy discussed earlier: dates are mapped to integer indices, a difference array is used to track frequency changes, and a prefix sum is applied to determine the most popular day:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


using namespace std;
using namespace std::chrono;

constexpr auto minDate = sys_days{year{2018}/month{1}/day{1}};
constexpr auto maxDate = sys_days{year{2020}/month{12}/day{31}};
constexpr auto totalDays = (maxDate - minDate).count() + 2;

auto dateToIdx(const std::string& s)
{
    int y, m, d;
    sscanf(s.c_str(), "%d-%d-%d", &y, &m, &d);
    return (sys_days{year{y}/month{m}/day{d}} - minDate).count();
}

std::string formatDate(const sys_days& date)
{
    auto ymd = year_month_day{date};
    std::ostringstream oss;
    oss << std::setfill('0') << std::setw(4) << int(ymd.year()) << "-"
        << std::setw(2) << unsigned(ymd.month()) << "-"
        << std::setw(2) << unsigned(ymd.day());
    return oss.str();
}

std::string solve(const std::vector<std::vector<std::string>>& reservations)
{
    array<int, totalDays> freqs{};
    
    for (const auto& r : reservations)
    {
        freqs[dateToIdx(r.front())]++;
        freqs[dateToIdx(r.back()) + 1]--;
    }
    
    std::partial_sum(freqs.begin(), freqs.end(), freqs.begin());
    int maxIdx = std::distance(freqs.begin(), std::max_element(freqs.begin(), freqs.end()));
    return formatDate(minDate + days{maxIdx});
}

For clarity, the prefix sum and maximum search are performed using std::partial_sum followed by std::max_element. These two steps could be merged into a single loop to avoid iterating twice over the array, but they are kept separate here for readability and brevity.

When latest additions to std::chrono are unavailable, we can still solve the problem efficiently using the old C tm structure. The idea is:

pick a fixed origin date (2018-01-01) and represent each date as the number of days since this origin;
build the difference array as before (for each reservation, add +1 at the start index and -1 at the day after the end index)
compute the prefix sum to determine the number of active reservations for each day
track the maximum value and return the corresponding date by converting the index back to a string.

This approach is still linear and uses \(O(D)\) memory, where \(D\) is the total number of days in the domain. It handles leap years correctly via mktime and avoids complex date arithmetic:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


constexpr int totalDays = 365 + 365 + 366 + 2;

time_t to_time(const string& s)
{
    tm t{};
    sscanf(s.c_str(), "%d-%d-%d", &t.tm_year, &t.tm_mon, &t.tm_mday);
    t.tm_year -= 1900;
    t.tm_mon -= 1;
    return mktime(&t);
}

string solve(const vector<vector<string>>& reservations)
{
    tm origin{};
    origin.tm_year = 2018 - 1900;
    origin.tm_mon = 0;
    origin.tm_mday = 1;
    time_t origin_time = mktime(&origin);

    array<int, totalDays> freqs{};

    for (const auto& r : reservations)
    {
        int start = (to_time(r.front()) - origin_time) / 86400; // 86400 is the number of seconds in one day
        int end   = (to_time(r.back())  - origin_time) / 86400 + 1;
        freqs[start]++;
        freqs[end]--;
    }

    int bestIdx = 0, maxCnt = 0, cur = 0;
    for (int i = 0; i < totalDays; ++i)
    {
        cur += freqs[i];
        if (cur > maxCnt)
        {
            maxCnt = cur;
            bestIdx = i;
        }
    }

    time_t result = origin_time + bestIdx * 86400;
    tm* out = localtime(&result);

    char buf[11]{};
    strftime(buf, sizeof(buf), "%Y-%m-%d", out);
    return buf;
}

Another approach consists in using a std::map, similarly of previous solutions (\(O(N log N)\)).The only function that we miss is that to calculate the next day for any given date. Doing this manually is straightforward and provides a good opportunity to practice handling leap years and month lengths:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


std::string getNextDay(const std::string& dateStr) 
{
    int y, m, d;
    sscanf(dateStr.c_str(), "%d-%d-%d", &y, &m, &d);
    
    // Days in each month
    const int daysInMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    // Check for leap year
    const bool isLeap = (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
    if (isLeap) 
        daysInMonth[1] = 29;
    
    // Increment day
    d++;
    
    // Check if we exceeded the month
    if (d > daysInMonth[m - 1])
    {
        d = 1;
        m++;
        
        // Check if we exceeded the year
        if (m > 12)
        {
            m = 1;
            y++;
        }
    }
    
    // Format back to string
    std::ostringstream oss;
    oss << std::setfill('0') << std::setw(4) << y << "-"
        << std::setw(2) << m << "-"
        << std::setw(2) << d;
    
    return oss.str();
}

string solve(const vector<vector<string>>& reservations)
{
    map<string, int> freqs;
    for (const auto& reservation : reservations)
    {
        freqs[reservation.front()]++;
        freqs[getNextDay(reservation.back())]--;
    }
    
    auto maxS = 0, rsum = 0;
    const std::string* best = nullptr;
    for (const auto& [date, freq] : freqs)
    {
        rsum += freq;
        if (rsum > maxS)
        {
            maxS = rsum;
            best = &date;
        }
    }
    
    return *best;
}

This solution works without any domain constraints.