Redução de MAX pra INTERVAL

O exercício 5 da lista de reduções pede para encontrar uma redução
linear do problema MAX (encontrar pontos maximais em um conjunto de pontos
no plano) para o problema INTERVAL (encontrar, em um conjunto de intervalos
na reta, aqueles que estão contidos em algum outro).

Uma solução que me propuseram é transformar os pontos (x, y) de entrada
do MAX em (-x, y) para entrar no INTERVAL. Na volta, seria só mudar de novo
o sinal de x para a saída do INTERVAL e remover os pontos resultantes do conjunto
inicial (deixando apenas os que não estão contidos em nenhum outro, isto
é, os maximais).

Isto parece funcionar muito bem para casos simples, como {(3, 4), (1, 2)}.
Neste caso, o 1o ponto domina o segundo (isto é, x1 >= x2 e y1 >= y2) e, na
forma de intervalo, [-1, 2] está contido em [-3, 4].

Agora para casos mais bizarros, como {(3, 4), (-200, -100)}, (onde, claramente,
o 1o domina o 2o), teríamos os intervalos [200, -100] e [-3, 4]. Se a verificação
de contingência do primeiro no segundo do algoritmo que resolve INTERVAL for
apenas checar se x1 >= x2 e y1 <= y2, tudo bem. Agora se ele também checar
se o intervalo é válido, isto é, se x1 <= y1 (e, por transitividade, se
x1 <= y2), não dá certo.

Alguém sabe como resolver para este caso? Ou uma redução diferente? Ou se
este caso na verdade funciona e eu estou viajando?