quick method count number of overlap intervals in an array of interval?

quick method count number of overlap intervals in an array of interval?

OK, this is a question I got for my advance algorithm class. I already
turned in my solution once but got rejected by my instructor due to
efficiency issue, in other words, I already made the efforts on my part
but could not get it even after his hint, so please be gentle. I will give
his hint below
Given an array of intervals with both start point and end point, find the
number of other intervals fall within it for each interval. number of
intervals is less than 10^9 and their ids are distinct. start and end are
less than 10^18, the input files don't contain duplicate number for start
and end. All the numbers above are integers
the hint is: considering a data structure with buckets. The algorithm
should be faster than O(n^2)
sample input and output
input:
5 %% number of intervals
2 100 200 %% id, start,end. all lines below follows this
3 110 190
4 105 145
1 90 150
5 102 198
output:
3 0
4 0
1 1
5 2
2 3