The set \(S\) of people we seek has the following characteristics.

• The minimum value of \(x\) among people in \(S\) is greater than the maximum value of \(x\) among people not in \(S\).
• The minimum value of \(y\) among people in \(S\) is greater than the maximum value of \(y\) among people not in \(S\).
• The minimum value of \(z\) among people in \(S\) is greater than the maximum value of \(z\) among people not in \(S\).
• \(S\) is the smallest non-empty set satisfying these conditions.

It suffices to sort by \((x, y, z)\) in descending order and check whether taking the first few elements satisfies these conditions.

The time complexity is \(O(N \log N)\).