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?


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.


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










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