Sorting by tuples [duplicate]

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 26 '18 at 1:17

• You are looking for maximal elements w.r.t. a partial order. Plenty of algorithms exist. – Raphael Jan 22 '18 at 6:11
• Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Jan 26 '18 at 1:13
• – D.W. Jan 26 '18 at 1:17

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$