This problem is from lintcode.
Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?
For interval list [[1,10],[2,3],[5,8],[4,7]], return 3
If landing and flying happens at the same time, we consider landing should happen at first.
Solution. This is a very interesting problem. The solution is that we can treat start of interval as left parenthesis, end of interval as right parenthesis. The problem will change to find the deepest parenthesis. In order to find the deepest inside parenthesis, we count how many left parenthesis it has. Once there is a right parenthesis, number of left parenthesis decrease 1.
Below is an example to calculate. We can see the max left is 3.
A tricky part is that we should take care of case of [[1, 3], [1, 3], [1, 3]]. This case return 3. In order to do that, I put <start, 1>, <end, -1> to a TreeMap. If there is already start in hashmap, then we should add <start, value_old + 1>. When we iterate all the parenthesis, we should add value instead 1 each time.
check my code on github: link