Problem
You are given a list of data entries that represent entries and exits of groups of people into a building. An entry looks like this:
{"timestamp": 1526579928, count: 3, "type": "enter"}
This means 3 people entered the building. An exit looks like this:
{"timestamp": 1526580382, count: 2, "type": "exit"}
This means that 2 people exited the building. timestamp
is in Unix time.
Find the busiest period in the building, that is, the time with the most people in the building. Return it as a pair of (start, end)
timestamps. You can assume the building always starts off and ends up empty, i.e. with 0 people inside.
Examples
Example 1
Input: [
{"timestamp": 1526579928, "count": 3, "type": "enter"},
{"timestamp": 1526580382, "count": 2, "type": "exit"},
{"timestamp": 1526580482, "count": 5, "type": "enter"},
{"timestamp": 1526581482, "count": 4, "type": "exit"}
]
Output: (1526580482, 1526581482)
Explanation: The building is busiest between timestamp 1526580482 and 1526581482 with 6 people inside.
Example 2
Input: [
{"timestamp": 1526572561, "count": 5, "type": "enter"},
{"timestamp": 1526575342, "count": 2, "type": "exit"},
{"timestamp": 1526578721, "count": 8, "type": "enter"},
{"timestamp": 1526582458, "count": 1, "type": "exit"},
{"timestamp": 1526587392, "count": 9, "type": "enter"}
]
Output: (1526578721, 1526582458)
Explanation: The building is busiest between timestamp 1526578721 and 1526582458 with 11 people inside.
Solution
Method 1 - Sorting
We can process the data entries in order of their timestamps and keep track of the number of people inside the building. By maintaining these counts, we can determine the period during which the count is at its highest.
Approach
- Sort the data entries by timestamp.
- Iterate through the sorted list and maintain a count of the number of people in the building:
- Increase the count for entries.
- Decrease the count for exits.
- Track the maximum number of people inside the building and the corresponding timestamps.
- Return the period that had the highest count of people.
Code
Java
public class Solution {
static class DataEntry {
int timestamp;
int count;
String type;
public DataEntry(int timestamp, int count, String type) {
this.timestamp = timestamp;
this.count = count;
this.type = type;
}
}
public int[] findBusiestPeriod(List<DataEntry> dataEntries) {
Collections.sort(dataEntries, Comparator.comparingInt(entry -> entry.timestamp));
int maxCount = 0;
int currentCount = 0;
int startTime = 0;
int endTime = 0;
for (int i = 0; i < dataEntries.size(); i++) {
DataEntry entry = dataEntries.get(i);
if (entry.type.equals("enter")) {
currentCount += entry.count;
} else {
currentCount -= entry.count;
}
// If it is the last entry or the next timestamp is different
if (i == dataEntries.size() - 1 || dataEntries.get(i + 1).timestamp != entry.timestamp) {
if (currentCount > maxCount) {
maxCount = currentCount;
startTime = entry.timestamp;
if (i < dataEntries.size() - 1) {
endTime = dataEntries.get(i + 1).timestamp;
} else {
endTime = entry.timestamp;
}
}
}
}
return new int[]{startTime, endTime};
}
public static void main(String[] args) {
Solution solution = new Solution();
List<Solution.DataEntry> entries = Arrays.asList(
new Solution.DataEntry(1526579928, 3, "enter"),
new Solution.DataEntry(1526580382, 2, "exit"),
new Solution.DataEntry(1526580482, 5, "enter"),
new Solution.DataEntry(1526581482, 4, "exit")
);
int[] result = solution.findBusiestPeriod(entries);
System.out.println(Arrays.toString(result)); // Output: [1526580482, 1526581482]
}
}
Python
class Solution:
def findBusiestPeriod(self, data_entries: List[Dict[str, int]]) -> Tuple[int, int]:
# Sort entries by timestamp
data_entries.sort(key=lambda x: x["timestamp"])
max_count = 0
current_count = 0
start_time = 0
end_time = 0
for i in range(len(data_entries)):
entry = data_entries[i]
if entry["type"] == "enter":
current_count += entry["count"]
else:
current_count -= entry["count"]
# If it's the last entry or the next entry has a different timestamp
if i == len(data_entries) - 1 or data_entries[i + 1]["timestamp"] != entry["timestamp"]:
if current_count > max_count:
max_count = current_count
start_time = entry["timestamp"]
end_time = data_entries[i + 1]["timestamp"] if i < len(data_entries) - 1 else entry["timestamp"]
return (start_time, end_time)
# Example usage
sol = Solution()
data_entries = [
{"timestamp": 1526579928, "count": 3, "type": "enter"},
{"timestamp": 1526580382, "count": 2, "type": "exit"},
{"timestamp": 1526580482, "count": 5, "type": "enter"},
{"timestamp": 1526581482, "count": 4, "type": "exit"}
]
print(sol.findBusiestPeriod(data_entries)) # Output: (1526580482, 1526581482)
Complexity
- ⏰ Time complexity:
O(n log n)
because of sorting the data entries. - 🧺 Space complexity:
O(1)
extra space, excluding the input space.