### Question

At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be accommodated as per their schedule.

Example: Time table is like below:

```
Bus Arrival Departure
BusA 0900 hrs 0930 hrs
BusB 0915 hrs 1300 hrs
BusC 1030 hrs 1100 hrs
BusD 1045 hrs 1145 hrs
```

The answer must be 3.

This question can also be in other forms:

Given a vector of Nodes, each of which contain the start and end time of a meeting, find the maximum number of rooms one would have to book for the day.

### Solution

The answer is same as finding the maximum number of bus at the bus-station at the same time.

**The suggestted solution** from here:

So first sort all the arrival(A) and departure(D) time in an int array. Please save the corresponding arrival or departure in the array also.

After sorting our array will look like this:

```
0900 0915 1930 1030 1045 1100 1145 1300
A A D A A D D D
```

Now use a counter. When sees an A, increment. When sees an D, decreament. In the end, return the largest counter value.

Note: If you have a arriving and a departing at same time, put departure time first.

### code

```
public int solve(List<Meeting> input) {
List<Event> events = new ArrayList<Event>();
for (Meeting i : input) {
events.add(new Event(i.start, 1));
events.add(new Event(i.end, -1));
}
Collections.sort(events);
int currentNeeds = 0;
int maxNeeds = 0;
for (Event e : events) {
currentNeeds += e.diff;
maxNeeds = Math.max(maxNeeds, currentNeeds);
}
return maxNeeds;
}
```

supporting classes:

```
class Event implements Comparable<Event> {
int time;
int diff;
// variable diff have value of 1 or -1
// when = 1, it means starting a meeting and 1 more room needed
// when = -1, it means ending a meeting and 1 less room needed
public Event(int a, int b) {
time = a;
diff = b;
}
@Override
public int compareTo(Event o) {
if (this.time == o.time) {
return this.diff - o.diff;
}
return this.time - o.time;
}
}
class Meeting {
int start;
int end;
public Meeting(int a, int b) {
start = a;
end = b;
}
}
```