This is my solution. first, sort the ids in terms of start time in ascending order second, sort the ids in terms of end time in descending order if the interval of one id_A falls into the interval of another id_B, then the start time of id_A should be after that of id_B, and the end time of id_ B should be after that of id_A. Therefore, we can use two loops to find out the number of ids that fall into any given id by searching the ordered id sequences. Time complexity is O(2log(n)+n^2) ~ O(n^2) For the given example, http://discuss.leetcode.com/questions/2274/count-number-of-over Start time sequence: 1 2 5 4 3 End time sequence: 2 5 3 1 4 output: 3 0 4 0 1 1 //id 4 falls in id 1; 5 2 //id 3,4 fall in id 5; 2 3 //id 5,4,3 fall in id 2
b*5
7 楼
人家是要小于n^2
id_ into
【在 c*****e 的大作中提到】 : This is my solution. : first, sort the ids in terms of start time in ascending order : second, sort the ids in terms of end time in descending order : if the interval of one id_A falls into the interval of another id_B, then : the start time of id_A should be after that of id_B, and the end time of id_ : B should be after that of id_A. : Therefore, we can use two loops to find out the number of ids that fall into : any given id by searching the ordered id sequences. : Time complexity is O(2log(n)+n^2) ~ O(n^2) : For the given example,