0

I have a searching problem like this:

"I have five lists of areas, namely list A, B, C, D and E. Each area has a radius and a center which occupies a round area in space. Let's place all areas in all lists on a 2-D map. Each overlaping region in a map is coded by the combination of names of the list of areas that creates the overlap (e.g., "ABCDE" or "ABDE"). How to find the overlapping regions with the the longest code? List them and their associated areas."

It seems like a 2-D version of this:

"Consider a big party where a log register for guest’s entry and exit times is maintained. Find the time at which there are maximum guests in the party. Note that entries in register are not in any order.

Example:

Input: 

   arrl[] = {1, 2, 9, 5, 5}
   exit[] = {4, 5, 12, 9, 12}

First guest in array arrives at 1 and leaves at 4, second guest arrives at 2 and leaves at 5, and so on. "

And the answer is here: http://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/

Anybody knows how to extend the answer to my original problem?

I can think of a brute force algorithm where I segment the whole map into many small squares and find the squares shadowed by the most areas. But it seems silly and time-consumming.

Thanks.

Tam Ho Huu Minh
  • 5
  • 1
  • 5
  • Smells like homework... Your problem is 1D not 2D ... time intervals overlap differently then circles ... brute force solution is `O(n^2)` if it is not enough for you you can create a 1D map (1D array) with small enough time step and each cell contains empty string. Then on each entry add ID to all cells that belong to it. after processing all entries search the map for longest string ...That is `O(n)` similar to this [Finding holes in 2d point sets?](https://stackoverflow.com/a/21884021/2521214) also if you do not need the string then you can use counter instead.... – Spektre May 31 '17 at 08:12
  • also this is similar [Location of highest density on a sphere](https://stackoverflow.com/a/25082674/2521214) – Spektre May 31 '17 at 08:16

0 Answers0