Skip to content

Travel plans 🚂

Scenario

You're helping a client plan a trip from New York to Paris, and they want you to find the fastest and cheapest routes.

They have collected journey information for routes that they are happy to take into two tables:

  • routes_timetable
  • routes_schedule

The timetable table records individual routes with their full departure/arrival timestamps and cost. The schedule table records the schedule of repeated routes with their schedule definition.

The earliest they can leave from New York is 2024-01-01 12:00:00-05:00.

Question

Given the tables that your client has provided, find the fastest and cheapest route from New York to Paris, leaving after 2024-01-01 12:00:00-05:00.

Give a minimum of 30 minutes and a maximum of 6 hours for "interchange" time, which is the time between arrival and departure at the same location. All costs are in the same currency (with no currency specified by the client).

The output should have at most two rows (the fastest/cheapest routes, which may be the same route), with the columns:

  • route which is each location in the route separated by a hyphen, e.g. New York - London - Paris
  • departure_datetime_utc as the departure time (UTC) from New York
  • arrival_datetime_utc as the arrival time (UTC) in Paris
  • duration as the total duration of the journey
  • cost as the total cost of the journey

Order the output by arrival_datetime_utc.

Expand for the DDL 
create table routes_schedule (
    schedule_id        int primary key,
    mode_of_transport  varchar not null,
    from_location      varchar not null,
    to_location        varchar not null,
    earliest_departure timetz not null,
    latest_departure   timetz not null,
    frequency          time,  /* `null` means that it's daily */
    duration           time not null,
    cost               decimal(8, 2) not null,
);
insert into routes_schedule
values
    (1, 'train', 'London St Pancras', 'London Gatwick',    '08:00:00+00:00', '20:00:00+00:00', '01:00:00', '00:30:00', 17.50),
    (2, 'train', 'London St Pancras', 'London Gatwick',    '07:30:00+00:00', '22:30:00+00:00', '02:30:00', '01:15:00', 12.00),
    (3, 'bus',   'London St Pancras', 'London Gatwick',    '06:15:00+00:00', '06:15:00+00:00', null,       '03:30:00',  6.75),
    (4, 'bus',   'London St Pancras', 'London Gatwick',    '19:30:00+00:00', '19:30:00+00:00', null,       '03:30:00',  6.75),
    (5, 'train', 'London Gatwick',    'London St Pancras', '09:00:00+00:00', '21:00:00+00:00', '01:00:00', '00:30:00', 17.50),
    (6, 'train', 'London Gatwick',    'London St Pancras', '07:15:00+00:00', '22:15:00+00:00', '02:30:00', '01:15:00', 12.00),
    (7, 'bus',   'London Gatwick',    'London St Pancras', '06:00:00+00:00', '06:00:00+00:00', null,       '03:30:00',  6.75),
    (8, 'bus',   'London Gatwick',    'London St Pancras', '20:00:00+00:00', '20:00:00+00:00', null,       '03:30:00',  6.75)
;

create table routes_timetable (
    route_id           int primary key,
    mode_of_transport  varchar not null,
    from_location      varchar not null,
    to_location        varchar not null,
    departure_datetime timestamptz not null,
    arrival_datetime   timestamptz not null,
    cost               decimal(8, 2) not null,
);
insert into routes_timetable
values
    (1,  'boat',  'London St Pancras', 'Paris',          '2024-01-01 06:00:00+00:00', '2024-01-01 07:30:00+01:00',  45.00),
    (2,  'plane', 'London Gatwick',    'New York',       '2024-01-01 13:05:00+00:00', '2024-01-01 20:55:00-05:00', 158.00),
    (3,  'plane', 'London Gatwick',    'New York',       '2024-01-02 20:40:00+00:00', '2024-01-03 04:30:00-05:00', 147.00),
    (4,  'plane', 'London St Pancras', 'Paris',          '2024-01-03 07:00:00+00:00', '2024-01-03 08:30:00+01:00',  70.00),
    (5,  'plane', 'Paris',             'New York',       '2024-01-02 12:00:00+01:00', '2024-01-02 20:30:00-05:00', 180.00),
    (6,  'plane', 'New York',          'London Gatwick', '2024-01-01 13:00:00-05:00', '2024-01-02 05:45:00+00:00', 160.00),
    (7,  'boat',  'New York',          'London Gatwick', '2024-01-01 05:30:00-05:00', '2024-01-01 23:00:00+00:00', 195.00),
    (8,  'boat',  'London St Pancras', 'Paris',          '2024-01-01 18:00:00+00:00', '2024-01-01 19:30:00+01:00',  95.00),
    (9,  'boat',  'London St Pancras', 'Paris',          '2024-01-02 14:00:00+00:00', '2024-01-02 15:30:00+01:00',  40.00),
    (10, 'plane', 'New York',          'Paris',          '2024-01-01 18:00:00-05:00', '2024-01-02 17:45:00+01:00', 279.00)
;

The solution can be found at:

Sample input

Routes Schedule

schedule_id mode_of_transport from_location to_location earliest_departure latest_departure frequency duration cost
1 train London Gatwick London St Pancras 09:00:00 +00:00 21:00:00 +00:00 01:00:00 00:30:00 12.25
2 bus London Gatwick London St Pancras 06:00:00 +00:00 06:00:00 +00:00 null 03:30:00 8.50

Routes Timetable

route_id mode_of_transport from_location to_location departure_datetime arrival_datetime cost
1 boat New York London Gatwick 2024-01-01T09:30Z 2024-01-01T22:00Z 179.00
2 plane New York London Gatwick 2024-01-01T23:00Z 2024-01-02T10:45Z 125.00
3 boat London St Pancras Paris 2024-01-02T13:00Z 2024-01-02T13:30Z 75.00 
with

routes_schedule(
    schedule_id,
    mode_of_transport,
    from_location,
    to_location,
    earliest_departure,
    latest_departure,
    frequency,
    duration,
    cost
) as (
    values
        (1, 'train', 'London Gatwick', 'London St Pancras', '09:00:00+00:00'::timetz, '21:00:00+00:00'::timetz, '01:00:00'::time, '00:30:00'::time, 12.25),
        (2, 'bus',   'London Gatwick', 'London St Pancras', '06:00:00+00:00'::timetz, '06:00:00+00:00'::timetz, null::time,       '03:30:00'::time,  8.50)
),

routes_timetable(
    route_id,
    mode_of_transport,
    from_location,
    to_location,
    departure_datetime,
    arrival_datetime,
    cost
) as (
    values
        (1, 'boat',  'New York',          'London Gatwick', '2024-01-01 04:30:00-05:00'::timestamptz, '2024-01-01 22:00:00+00:00'::timestamptz, 179.00),
        (2, 'plane', 'New York',          'London Gatwick', '2024-01-01 18:00:00-05:00'::timestamptz, '2024-01-02 10:45:00+00:00'::timestamptz, 125.00),
        (3, 'boat',  'London St Pancras', 'Paris',          '2024-01-02 13:00:00+00:00'::timestamptz, '2024-01-02 14:30:00+01:00'::timestamptz,  75.00)
)
Sample output
route departure_datetime_utc arrival_datetime_utc duration cost
New York - London Gatwick - London St Pancras - Paris 2024-01-01 23:00:00 2024-01-02 13:30:00 14:30:00 212.25 
solution(route, departure_datetime_utc, arrival_datetime_utc, duration, cost) as (
    values
        ('New York - London Gatwick - London St Pancras - Paris', '2024-01-01 23:00:00'::timestamp, '2024-01-02 13:30:00'::timestamp, '14:30:00', 212.25);
)
Hint 1

Expand the routes_schedule table into individual routes and then union with the routes_timetable table for a full list of routes to consider.

Hint 2

Use a recursive CTE to build up the journey from New York to Paris, considering the interchange time between routes.