OK, I think I found something this time.

We start by sorting the tuples based on the first element. This can be done in $O(n\log n)$.

The first tuple of the sorted list is certainly in your set. The second tuple is in your set if the second element of that tuple is larger than or equal to the second element of the first tuple. And more generally: any tuple in the list is in the set if its second element is larger than or equal to the maximum of the second elements of the previous tuples. So you can go through the list, storing the maximum of the second elements as you go along and add each tuple to the set if its second element is larger than or equal to the maximum you have at that point. This has complexity $O(n)$.

This gives a total complexity of $O(n\log n)$.