title: GTFS - Improving search for trips in two feeds
body: <p>I'm currently working on a java program that takes in two feeds and prints out the trips that are missing in either of the feeds or are partially in it. For example Feed 1 has a trip T1 with the stops ABCDE and Feed 2 has a trip T2 with the stops ABCD. So T2 is a subset of T1.</p>
  
  <p>I basically have one <code>Map&lt;Type, List&lt;Trip&gt;&gt;</code> for each feed. The Type is the route type (bus, tram,  etc.) and the <code>List&lt;Trip&gt;</code> contains all trips of that type.</p>
  
  <p>All <code>Trip</code> objects have the fields that are specified <a href="https://developers.google.com/transit/gtfs/reference/trips-file" rel="nofollow noreferrer">here</a>. And also a reference to a <code>List&lt;StopTime&gt;</code> and  a <code>Service</code> which specifies the stops in sorted order and the service times when the trip is running.</p>
  
  <p>The check works as intended and I get the results I expect. But running time with large feeds (40.000 and more trips) is quite long, because i basically check every trip from one list with the other which would be O(n^2) in the worst case if I'm not mistaken.</p>
  
  <p>I'm looking for a way to minimize the trips I have to look at.
  One thing that I could do is to move the check if the date ranges of the trips overlap.This is currently done when checking the <code>List&lt;StopTime&gt;</code>within the <code>Trip</code> object. </p>