Issue
If you have a set of ranges, such as the following simple example…
[
[12, 25], #1
[14, 27], #2
[15, 22], #3
[17, 21], #4
[20, 65], #5
[62, 70], #6
[64, 80] #7
]
… how do you compute the maximally intersecting subset (not sure quite how to phrase it, but I mean “the subset of ranges which intersects and has the highest cardinality”) and determine the degree of intersection (cardinality of ranges in that subset)?
Logically I can work it out, and might be able to translate that to a naive algorithm. Going down the list, we see that 15 intersect, and 57 intersect, and that #5 intersects both sets.
The result I want is simply the subset, since that gives me the information about the cardinality, and I can easily compute the intersection of the set as long as they all intersect. In the above example, it would be [[14, 27],[15, 22],[12, 25],[17, 21],[20, 65]]
.
Off the top of my head, I might try converting each range to a graph node, connecting the ones which are intersecting, and finding the largest fullyconnected graph.
I was also thinking iteratively to start at the beginning, continue building up a list of intersecting ranges with a running intersection on each to check againstâ€”until you hit an element which doesn’t intersect, then start a new list. Continue checking each item against the existing intersections. However I’m not sure this is complete.
I could take a stab at implementing something (lang is ruby FWIW), but I would love to hear how others might solve this problem, and what the most efficient and elegant way might be.
Update:
I believe this is a specific case of the Maximum clique problem, which is NPhard and thus actually difficult. Suggestions for approximations/realworld use would be most appreciated!
See also: http://en.wikipedia.org/wiki/Maximum_clique / Find all complete subgraphs within a graph
Update 2
Found a nice proof of this problem’s NPhardness and NPcompleteness here: http://www.cs.bris.ac.uk/~popa/ipl.pdf
Looks like this is the end of the line then. Sorry folks! I’ll work with a goodenough greedy approximation. Thanks.
As said in the answers I don’t think that paper describes this problem… we probably have more information here based on the ranges.
Solution
If I understand the problem correctly, it is not an instance of the NP problem described in the paper you linked to. Here is my understanding of the problem, and a polynomialtime solution.

We are given a finite set of ranges of real numbers, say n: [A_{1}, B_{1}], [A_{2}, B_{2}], …, [A_{n}, B_{n}], where A_{i} â‰¤ B_{i}.

Create a sorted list of the starting and ending points, ordered numerically, indicating whether the point is a starting or ending point.
In your example, this would be: 12+, 14+, 15+, 17+, 20+, 21, 22, 25, 27, 62+, 64+, 65, 70, 80

Initialize
curOverlap
andmaxOverlap
to zero. 
Iterate through the list, incrementing
curOverlap
for each + and decrementing it for each . SetmaxOverlap = max(curOverlap, maxOverlap)
on each increment.
To continue your example:
val, cur, max
12, 1, 1
14, 2, 2
15, 3, 3
17, 4, 4
20, 5, 5
21, 4, 5
22, 3, 5
25, 2, 5
27, 1, 5
62, 2, 5
64, 3, 5
65, 2, 5
70, 1, 5
80, 0, 5
The max overlap is 5. You could also store the val associated with the max if you wanted to know where the max overlap occurred. That would give you 20. in this example. It’s then trivial to go through the initial set of ranges and find the 5 which include 20.
edit If you have repeated values, count the plusses before the minuses for each value so that you include ranges that overlap at a single point.
Answered By – Dave
Answer Checked By – Katrina (AngularFixing Volunteer)