For the NumberOfDiscIntersections problem of Codility site. it's a little hard to figure it out.
At first, I use bruce force method to solve it, the complexity is O(n^^2)
On the web page, they require the worst complexity is O(nlogn), so we need find a better solution.
I searched on web, many people have a solution which sort the boundary of disc, and its complexity is O(nlogn), it suggest to use binary search whose complexity is O(logn), so I try and got this:
We first sort the left boundarys, and and then in a loop to find each right boundary's position in it(using binary search), as the loop is O(n), and binary search is O(logn), so the total complexity is O(nlogn)
But do we still have a better solution?
We can consider the discs as events. for each disc, so each disc has 2 events: open event, and close event. And then we can use stack to trace the events. when a disc open, we push a record, when another disc open, we check how many records are there in the stack, that means the intersection, and when a disc close, we pop the stack.
Now the complexity is O(n) now.