1
$\begingroup$

This question already has an answer here:

This is more of a practical question for me, but I have a few team members $n$ who I'd like to sort by two characteristics (just call them $a$ and $b$ for now). These characteristics are just a rating (given from 1-10). Among these $n$ team members, I am trying to find those who fit a definition of being good i.e. given a team member $i$, there is no team member $i'$ who has both a higher $a$ rating and a higher $b$ rating. There can by many people who would fit this definition of good.

Not sure if this qualifies as a sorting problem or not, but basically I think I have an intuition for it: I was thinking about first sorting by the $a$ values. And then somehow using that information, I was thinking about sorting by the $b$ values but using the $a$ values somehow conditionally to determine swaps in positions. Does anyone have a good idea of how to boil this down to a problem that's a bit easier to think about/more common?

$\endgroup$

marked as duplicate by D.W. algorithms Jan 26 '18 at 1:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

The problem can be solved in $\mathcal{O}(n\log{}n)$. I don't know if there are faster solutions.

Assume all $a$ ratings to be distinct, the general case can be solved in the same way with little modifications.

We say that a member $j$ is $\textit{better }$than a member $i$ if $\;(a_i<a_j \wedge b_i<b_j)$. Obviously a member is $\textit{good}$ if there aren't members $\textit{better}$ than him.

The idea is to first sort in ascending order by $a$ rating. The key observation is:

  • Fixed a member $i$, there is a member $j \textit{ better}$ than him if and only if $\;i<j\:\wedge\:b_i<b_j$

In other words if, for each member $i$, we know $\max\limits_{i<j}\{b_j\}$ we can deduce if $i$ is $\textit{good}$ or not.

The idea in pseudocode



$N\gets{}|\mathcal{Members}|$

$Sort(\mathcal{Members})$

$MAX\gets{}\mathcal{Members}[N].b$

$\mathcal{Members}[N].is\_good\gets{}\texttt{true}$

$\textbf{for}\;\;i\gets{}N\!-\!1\;\;\textbf{to}\;\;1\;\;\textbf{do}$

$\qquad\textbf{if}\;\;\mathcal{Members}[i].b\geq{}MAX\;\;\textbf{then}$

$\qquad\qquad\mathcal{Members}[i].is\_good\gets{}\texttt{true}$

$\qquad\qquad{}MAX\gets{}\mathcal{Members}[i].b$



$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.