I have a problem

I have a problem. I spend a lot of time looking at flight prices and thinking about whether I should travel or not.

I spend a lot of time at Kayak. Every week, I read my domestic and international fare deals from SmarterTravel.com.

One thing I don't get is why I will sometimes see longer, more expensive flights that take off earlier and land later listed by the same airline on a search. For example, let's say I'm traveling to Pittsburgh, I just saw these two flight options listed:

Flight 1, US Airways, departs SFO 10:30pm, lands PIT 6:00 am. $499
Flight 2, US Airways, departs SFO 8:00pm, goes through Chicago, lands PIT 7:00am. $509

Now, I don't know about you, but I'd prefer flight 1 (too bad United has flights for half price that aren't direct). Well, I would go so far to say I don't want to see flight 2 in my results - I have to be at SFO earlier, I land at Pittsburgh later, and I pay more money.

However, people have departure time needs. People want to arrive by a certain time. People have airline preferences. And they don't want their searches to be more complex. I propose that an airline search doesn't even display flights that take off earlier, land later, and cost more that are on the same airline.

This creates another problem. What if I book a couple days after my friend does, and I want the more expensive, less useful flights so I can be on the same flight as him. How do we avoid users being confused that what was an option now isn't?

People who look for the cheapest, or direct with less regard to cost, flights won't often notice the longer flight, more money problem - it's people who are optimizing for both time and money who will. So this is a smaller crowd we're talking about.

I've included pseudocode about the first way I can think to filter. I can't figure out how to make this any better than O(number of flights^2) (but I've only spent 10 minutes), though with airlines separated, it gets to be a bit more reasonable in the real world.

List<flight> logicalChoices = new List<flight>();

for (Airline airline : airlines) {
  flights = search(departureDateRange, departureAirport,
                   arrivalTimeRange, arrivalAirport, 
                   airline);
  flights.sortByPriceAscending();
  for (i=0; i < flights.length; i++) {
    boolean displayFlight = true;
    for (int j = 0; j < i; j++) {
      if (flight[j].totalDuration < flight[i].totalDuration
              && flight[j].departureTime > flight[i].departureTime
              && flight[j].arrivalTime < flight[i].arrivalTime) {
        // assert flight[j].price < flight[i].price - ordered by price asc
        displayFlight = false;
        break;
      }
    }
    if (displayFlight) {
      logicalChoices.add(flight[i]); 
    }
  }
}

Display logicalChoices to user