Compute maximum simultaneous bus routes
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given N bus routes, each defined by a start time (inclusive) and an end time (exclusive). Compute the maximum number of routes running simultaneously. Clarify your algorithm, justify correctness, and analyze time and space complexity.
Overview: This question evaluates algorithmic proficiency with interval overlap counting and concurrent event aggregation, emphasizing correctness reasoning and time/space complexity analysis. It falls under the Coding & Algorithms domain and is commonly asked to assess practical algorithm implementation and complexity-analysis skills rather than purely conceptual understanding.
You are given a list of bus routes, where each route is represented by a pair (start, end). A route is active from its start time inclusive to its end time exclusive, meaning it covers the interval [start, end). Compute the maximum number of routes running at the same time.
Because the input can be large, your solution should be more efficient than checking every pair of routes. If the list is empty, return 0.
Important: since end times are exclusive, a route ending at time t does not overlap with a route starting at time t.
Constraints
- 0 <= len(routes) <= 200000
- 0 <= start < end <= 1000000000
- All start and end values are integers
Examples
Input: []
Expected Output: 0
Explanation: There are no routes, so the maximum number running at the same time is 0.
Input: [(10, 20)]
Expected Output: 1
Explanation: A single route is active by itself, so the maximum overlap is 1.
Hints
- Instead of comparing every pair of routes, sort all start times and end times separately and scan through them with two pointers.
- Since end times are exclusive, if a start time equals an end time, process the ending route first.
Community answers
Answer by goel.radhika91
Arrays.sort(routes, ( x, y) -> x[0] - y[0]);
int maxBuses = 0;
int maxInterval = 0;
for (int[] interval: routes) {
maxInterval = Math.max(maxInterval, interval[1]);
}
int[] numberLine = new int[maxInterval];
for (int[] interval: routes) {
int start = interval[0];
int end = interval[1];
for (int i = start; i < end ; i++) {
numberLine[i] += 1;
}
}
for (int i = 0; i < numberLine.length; i++) {
if (numberLine[i] >= 1) {
maxBuses = Math.max(maxBuses, numberLine[i]);
}
}
return maxBuses;