Compute peak parking lot occupancy intervals

You are given logs from a parking lot system. Each log entry has the form:

[carId, time, eventType]

• carId is an integer identifying a car.
• time is an integer timestamp (e.g., minutes or hours).
• eventType is a string, either 'entry' or 'exit'.

Example log list:

[[1, 1, 'entry'], [1, 11, 'entry'], [1, 10, 'exit'], [2, 20, 'exit']]

You can assume:

• The log list may be unsorted by time.
• For questions (1) and (2) below, every 'entry' has a matching 'exit' for that carId, and exits happen after their corresponding entries.
• A car cannot re-enter the lot before it has exited (i.e., intervals for the same carId do not overlap).
• Multiple events can occur at the same timestamp. For counting occupancy, treat all 'exit' events at a given timestamp as happening just before any 'entry' events at that same timestamp.

Answer the following:

1. Maximum occupancy count Compute the maximum number of cars that are in the parking lot at the same time over the entire time range covered by the logs. Return this maximum count as an integer.

2. Intervals with maximum occupancy Find the time interval or intervals during which the number of parked cars is equal to the maximum from (1). Represent each interval as [startTime, endTime), where:

   • startTime and endTime are integer timestamps,
   • the car count is constant and equal to the maximum for all times in [startTime, endTime),
   • the interval is maximal (you cannot extend it to the left or right without lowering the count).

   If there are multiple disjoint intervals with the same maximum occupancy, return all of them.

3. Maximum occupancy when some exits are missing Now suppose the 'exit' scanner is faulty: some 'exit' events are missing from the logs, but all 'entry' events are still recorded correctly.

   The parking lot has a policy that no car may stay longer than 2 hours. Formally, for each car:

   • Its true parking interval is [entryTime, actualExitTime),
   • entryTime is the time in its logged 'entry' record,
   • if an 'exit' record exists, then actualExitTime is the time in that record,
   • if an 'exit' record is missing, then actualExitTime is some unknown time satisfying:

$entryTime < actualExitTime \le entryTime + 2$

Under these conditions, you do not know the exact exit times for cars with missing exit logs, only that each such car must leave within 2 hours of its entry.

Design an algorithm that, given this incomplete log data and the 2‑hour constraint, computes the time interval or intervals during which the parking lot could have the largest possible number of cars parked simultaneously, assuming the (unknown) exit times are chosen adversarially (or optimally) to maximize the peak occupancy, but must still satisfy the constraints above.

As in (2), return the interval(s) as [startTime, endTime) with maximum possible occupancy.

Describe your algorithm(s), including time and space complexity, for all three subproblems.

Peak Parking Lot Occupancy Intervals

Constraints

• Logs may be unsorted
• Intervals are half-open [entry, exit)

Hints

1. Convert car logs to intervals, then sweep timestamp deltas with exits before entries.