figuring out if a seat is available for a specific itinerary

Question

So I've got an interesting problem here that I'd like to find an elegant solution to. In this case, I don't really have any code written as what I'm looking for is more of an algorithm. Once I know how to do it, I should be able to translate into a programming language. So here's the deal:

Suppose you have a train with 3 seats that travels to 6 stations (the numbers can vary here, but if it works for these numbers, it should work for all of them and I think it helps to have actual numbers to better understand the problem).

So we have seat 1, 2 and 3 and stations A, B, C, D, E, F

A person can come in at any station to travel to a station that's further away. There's no loop here so you can't travel F ---> A (It also means that no one's going to be coming in at station F).

Also, and I'm not certain how to phrase this, but seats are not "assigned" so to speak. Basically, if a person wants to go A-->C and seat 1 is available A-->B and seat 2 is available B-->C then we consider there's indeed space for the person to ride (basically a person will just walk in and seat on whatever seat's available).

So now, my problem is that I'd like to know how many seats are available for a given itinerary at any time.

As you can tell, if I have three people going A-->F then I'm full, no one can get in.

However, if I have

A-->C
A-->B
A-->E
B-->D

Then I have like 2 seats 1 seat available if I want to go C-->D or 1 seat none available if I want to go B-->D and so on and so forth. As you can tell, things get really complicated really fast so I need an algorithm that would efficiently allow me to calculate this.

Right now, the only solution I could find is this (in pseudo-code):

itinerary = x-->y

for stations s going from x to y
    seatsAvailable[s] = 3 - count reservations starting at or before x and ending after x

availableSeats = min(seatsAvailable);

Answer 1

'my problem is that I'd like to know how many seats are available for a given itinerary at any time.', since your train is only one way I think that time does not have any importance in your problem, if you are using some type of object-oriented programming you can add a variable empty sets that is a simple integer where if someone gets in the train it increases with one and decreases by one else where, to know the number of empty seats at a given station A you can do number_of_empty_seats=total_number_of_seats-(number_of_itinerary_that_end_by_A + number_of_itinerary_that_end_BEFOR_A).

Answer 2

Your pseudo code looks fine, although the step "count reservations" would need to be expanded in more detailed code as it would involve a loop.

You can improve a bit, by counting those reservations incrementally as you loop through the stations, so combining that counting with also tracking the minimum number of seats available. In order to incrementally update the number of free seats, you would first store the changes to the number of free seats at each station (+1 or -1 for each trip).

For large inputs, you would probably have to look into interval trees, but given that the numbers involved in your scenarios are tiny (in comments you mention numbers that are not greater than 10), that would be counter productive: the overhead of managing that interval tree would be more costly than what you gain.

So here is the proposed algorithm in a JavaScript implementation:

function getNumFreeSeatsOnTrip(numSeats, trips, newTrip) {
    // Determine the number of seats that are free at each station
    const changeSeats = Array(newTrip.hopOff).fill(0);
    for (const trip of trips) {
        if (trip.hopOn < newTrip.hopOff) {
            changeSeats[trip.hopOn]--;
        }
        if (trip.hopOff < newTrip.hopOff) {
            changeSeats[trip.hopOff]++;
        }
    }
    // Determine the number of free seats at start of the new trip
    let seats = numSeats;
    for (let station = 0; station <= newTrip.hopOn; station++) {
        seats += changeSeats[station];
    }
    // Determine minimum of number of free seats during the new trip
    let minSeats = seats;
    for (let station = newTrip.hopOn + 1; station < newTrip.hopOff; station++) {
        seats += changeSeats[station];
        minSeats = Math.min(minSeats, seats);
    }
    return minSeats;
}

// Main:
const numSeats = 3;
const trips = [
    { hopOn: 0, hopOff: 2 }, // A-->C
    { hopOn: 0, hopOff: 1 }, // A-->B
    { hopOn: 0, hopOff: 4 }, // A-->E
    { hopOn: 1, hopOff: 3 }, // B-->D
];
const newTrip = { hopOn: 2, hopOff: 3 }; // C-->D
const freeSeats = getNumFreeSeatsOnTrip(numSeats, trips, newTrip);
console.log("free seats for trip from station 2 to 3:", freeSeats);

So the example here is depicted like this:

Station:     0     1     2     3     4
trip 1       on XxxxxxX off 
trip 2       on X off
trip 3       on XxxxxxXxxxxxXxxxxxX off
trip 4             on XxxxxxXxxxxxX off
-------------------------------------
free seats:     0     0     1     1

So in this example set up, no additional trip can start at stations 0 or 1 (A or B).