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:

1

{"timestamp": 1526579928, count: 3, "type": "enter"}

This means 3 people entered the building. An exit looks like this:

1

{"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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7
8
9

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

  1. Sort the data entries by timestamp.
  2. 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.
  3. Track the maximum number of people inside the building and the corresponding timestamps.
  4. Return the period that had the highest count of people.

Code

 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

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]
    }
}
 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

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.