Sorting by tuples [duplicate]

Question

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?

Answer 1

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$

---

---