I have a matrix in the following form:ID | # Counts for ID | ID's Within Range.1  | 5               | 1,2,3 2  | 3               | 1,23  | 2               | 1,3....The idea is that I want to find the 2 id's that when you sum the have the highest count. However, you must first exclude the pairs that overlap. For instance, id's 1 and 2 have the highest count but you can't use them since 1 has 2 within range and 2 has 1 within range. Thus from the table above you would use 2,3 as the sum since they don't overlap.I would like to do this in O(n) or O(nlogn) time and O(n) storage. It's trivial to do if I first make all ID pairs but that gives me O(n^2). I can also do 2 forloops after sorting the list but that would also be at worst O(n^2) although usually much faster... Any help would be greatly appreciated! THanks!
Finding max of two elements in linear time with restriction
ds.algorithms;time complexity;sorting
Ok, so as I understand it, you are given as input an undirected graph (representing the within range restrictions) with weights on its vertices, and you want to find a non-adjacent pair of vertices that has maximum total weight. I'm going to interpret linear time as being linear in the number of edges in the input graph, not just the number of vertices, because otherwise it doesn't make sense  you need to have enough time to be able to look at the whole input.Here's an $O(m+n)$ time solution (simplifying an earlier solution I posted here):Assume for simplicity that $n$ is a power of two (if not round up).Find the median of the vertex weights, the median of the highest $n/2$ vertex weights, the median of the highest $n/4$ vertex weights, etc. These median computations take a total of $O(n)$ time, and once completed they give you the set of $2^i$ largest weights for every choice of an integer $i$ For each vertex $v$ with degree $d_v$, let $i_v=\lceil\log_2(d_v+1)\rceil$. Form the pairs $(v,w)$ where $w$ is in the set of $2^{i_v}$ largest vertex weights found during the median calculations.From the sets of pairs found in the previous step, remove the pairs that correspond to adjacent pairs of vertices (either by using a hash table of edges for fast adjacency lookup, or by using two passes of bucket sort to make a sorted list of both pairs and input edges).The remaining pairs for each vertex $v$ necessarily include the heaviest nonadjacent neighbor of $v$. In particular the heaviest nonadjacent pair in the whole graph is somewhere in this list of pairs. Compute the weight for each pair and choose the max.