Skip to content

4080. Design Bus Seat Booking System

DifficultyMedium

Description

You are asked to design a seat booking system for a bus.

The bus has n rows. Each row has four seats labeled "A", "B", "C", and "D".

Seats "A" and "D" are window seats; seats "B" and "C" are middle seats. In each row, seat "A" is adjacent to seat "B", and seat "D" is adjacent to seat "C".

Booking rules:

  • Booking a middle seat ("B" or "C") always takes 1 second.
  • Booking a window seat ("A" or "D") takes 1 second if its adjacent middle seat is not booked, or 3 seconds (an extra delay of 2 seconds) if its adjacent middle seat is already booked.

A seat is identified by a string such as "A1" or "D20" (one letter from A to D followed by its row number).

Implement the BusBooking class:

  • BusBooking(int n): Initializes the system with n empty rows.
  • void toggle(string seat): Books seat if it is free, or frees it if it is already booked.
  • int getTotalTime(): Returns the total time (in seconds) taken to book all currently booked seats, where the seats are booked in the order their toggle calls were made. If no seats are currently booked, return 0.
  • int getMinTime(): Returns the smallest possible total time (in seconds) to book all currently booked seats, over every possible order of booking them. If no seats are currently booked, return 0.

Note: The time cost of a seat is fixed at the moment it is booked, based on the seats booked at that time. Booking or freeing other seats afterward does not change the cost of a seat that is already booked.

 

Example 1:

Input:
["BusBooking", "toggle", "toggle", "getTotalTime", "getMinTime", "toggle", "toggle", "getTotalTime", "getMinTime"]
[[20], ["B3"], ["A3"], [], [], ["C3"], ["D3"], [], []]

Output:
[null, null, null, 4, 2, null, null, 8, 4]

Explanation

BusBooking busBooking = new BusBooking(20); // start with 20 empty rows
busBooking.toggle("B3"); // book "B3", a middle seat, which costs 1 second. Total time is now 1.
busBooking.toggle("A3"); // book "A3", a window seat. Its adjacent middle "B3" is already booked, so it costs 3 seconds. Total time is now 1 + 3 = 4.
busBooking.getTotalTime(); // return 4, since in toggle order "B3" costs 1 and "A3" costs 3.
busBooking.getMinTime(); // return 2. Booking "A3" before "B3" avoids the delay, so 2 seats takes 2 second to book.
busBooking.toggle("C3"); // book "C3", a middle seat, which costs 1 second. Total time is now 1 + 4 = 5.
busBooking.toggle("D3"); // book "D3", a window seat. Its adjacent middle "C3" is already booked, so it costs 3 seconds. Total time is now 5 + 3 = 8.
busBooking.getTotalTime(); // return 8, since in toggle order the seat costs are 1, 3, 1, 3.
busBooking.getMinTime(); // return 4. With the best possible booking order, no delay is added, so the 4 booked seats take 4 * 1 = 4 seconds.

Example 2:

Input:
["BusBooking", "toggle", "toggle", "getTotalTime", "toggle", "toggle", "toggle", "getTotalTime", "getMinTime"]
[[10], ["C7"], ["D7"], [], ["D7"], ["C7"], ["D7"], [], []]

Output:
[null, null, null, 4, null, null, null, 1, 1]

Explanation

BusBooking busBooking = new BusBooking(10); // start with 10 empty rows
busBooking.toggle("C7"); // book "C7", a middle seat, which costs 1 second. Total time is now 1.
busBooking.toggle("D7"); // book "D7", a window seat. Its adjacent middle "C7" is already booked, so it costs 3 seconds. Total time is now 1 + 3 = 4.
busBooking.getTotalTime(); // return 4, since in toggle order "C7" costs 1 and "D7" costs 3.
busBooking.toggle("D7"); // "D7" is already booked, so free it. This removes its cost of 3. Total time is now 4 - 3 = 1.
busBooking.toggle("C7"); // "C7" is already booked, so free it. This removes its cost of 1. Total time is now 1 - 1 = 0, and row 7 is empty.
busBooking.toggle("D7"); // book "D7" again, a window seat. Its adjacent middle "C7" is not booked this time, so it costs only 1 second. Total time is now 0 + 1 = 1.
busBooking.getTotalTime(); // return 1, since only "D7" is booked and it cost 1 this time.
busBooking.getMinTime(); // return 1. With the best possible booking order, the 1 booked seat takes 1 * 1 = 1 second.

 

Constraints:

  • 1 <= n <= 105​​​​​​​
  • seat[0] is one of 'A', 'B', 'C', 'D'.
  • The remaining characters of seat form an integer row with 1 <= row <= n.
  • The total number of calls to toggle, getTotalTime, and getMinTime does not exceed 105.

Solutions

Solution 1: Record the Booking Cost

Thinking

Both the number of rows and the number of calls can reach \(10^5\), so replaying the whole booking history on every query exceeds the limit.

A window seat costs an extra \(2\) seconds only when its adjacent middle seat is already booked, and that cost is fixed at the moment \(\textit{toggle}\) books it. \(\textit{getTotalTime}\) is the sum of the costs recorded for the seats that are still occupied.

\(\textit{getMinTime}\) may reorder the booking of those seats. A middle seat always costs \(1\) second; booking a window seat before its adjacent middle seat avoids the extra \(2\) seconds. The minimum time is therefore the number of seats currently booked. Store each seat's cost from the moment it was booked, keep the total and the occupancy count separately, and every operation is \(O(1)\).

Each row is stored as an array of length \(4\). A cell value of \(0\) means the seat is free; otherwise it is the number of seconds fixed when that seat was booked. The variable \(\textit{tot}\) keeps the sum of these costs, and a counter keeps the number of seats currently booked.

When \(\textit{toggle}\) sees a booked seat, subtract its stored cost from \(\textit{tot}\), decrease the counter, and clear the cell. When the seat is free, a middle seat \(\texttt{B}\) or \(\texttt{C}\) costs \(1\) second. A window seat \(\texttt{A}\) or \(\texttt{D}\) costs \(3\) seconds if its adjacent middle seat is already booked, and \(1\) second otherwise. Write that cost into the array and update both \(\textit{tot}\) and the counter.

\(\textit{getTotalTime}\) returns \(\textit{tot}\), and \(\textit{getMinTime}\) returns the number of booked seats.

Each operation takes \(O(1)\) time, and the space complexity is \(O(n)\), where \(n\) is the number of rows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class BusBooking:
    def __init__(self, n: int):
        self.tot = 0
        self.min_tot = 0
        self.cost_data = [[0] * 4 for _ in range(n)]

    def toggle(self, seat: str) -> None:
        i = int(seat[1:]) - 1
        j = ord(seat[0]) - ord("A")
        if self.cost_data[i][j] > 0:
            self.min_tot -= 1
            self.tot -= self.cost_data[i][j]
            self.cost_data[i][j] = 0
            return
        cost = 1
        if (j == 0 and self.cost_data[i][1] > 0) or (
            j == 3 and self.cost_data[i][2] > 0
        ):
            cost = 3
        self.min_tot += 1
        self.tot += cost
        self.cost_data[i][j] = cost

    def getTotalTime(self) -> int:
        return self.tot

    def getMinTime(self) -> int:
        return self.min_tot


# Your BusBooking object will be instantiated and called as such:
# obj = BusBooking(n)
# obj.toggle(seat)
# param_2 = obj.getTotalTime()
# param_3 = obj.getMinTime()
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class BusBooking {
    private int tot;
    private int minTot;
    private int[][] costData;

    public BusBooking(int n) {
        this.tot = 0;
        this.minTot = 0;
        this.costData = new int[n][4];
    }

    public void toggle(String seat) {
        int i = Integer.parseInt(seat.substring(1)) - 1;
        int j = seat.charAt(0) - 'A';
        if (costData[i][j] > 0) {
            minTot -= 1;
            tot -= costData[i][j];
            costData[i][j] = 0;
            return;
        }
        int cost = 1;
        if ((j == 0 && costData[i][1] > 0) || (j == 3 && costData[i][2] > 0)) {
            cost = 3;
        }
        minTot += 1;
        tot += cost;
        costData[i][j] = cost;
    }

    public int getTotalTime() {
        return tot;
    }

    public int getMinTime() {
        return minTot;
    }
}

/**
 * Your BusBooking object will be instantiated and called as such:
 * BusBooking obj = new BusBooking(n);
 * obj.toggle(seat);
 * int param_2 = obj.getTotalTime();
 * int param_3 = obj.getMinTime();
 */
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class BusBooking {
private:
    int tot;
    int min_tot;
    vector<array<int, 4>> cost_data;

public:
    BusBooking(int n) {
        tot = 0;
        min_tot = 0;
        cost_data = vector<array<int, 4>>(n, {0, 0, 0, 0});
    }

    void toggle(string seat) {
        int i = 0;
        for (int k = 1; k < seat.size(); k++) {
            i = i * 10 + (seat[k] - '0');
        }
        i -= 1;
        int j = seat[0] - 'A';

        if (cost_data[i][j] > 0) {
            min_tot -= 1;
            tot -= cost_data[i][j];
            cost_data[i][j] = 0;
            return;
        }

        int cost = 1;
        if ((j == 0 && cost_data[i][1] > 0) || (j == 3 && cost_data[i][2] > 0)) {
            cost = 3;
        }
        min_tot += 1;
        tot += cost;
        cost_data[i][j] = cost;
    }

    int getTotalTime() {
        return tot;
    }

    int getMinTime() {
        return min_tot;
    }
};

/**
 * Your BusBooking object will be instantiated and called as such:
 * BusBooking* obj = new BusBooking(n);
 * obj->toggle(seat);
 * int param_2 = obj->getTotalTime();
 * int param_3 = obj->getMinTime();
 */
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
type BusBooking struct {
    tot      int
    minTot   int
    costData [][]int
}

func Constructor(n int) BusBooking {
    costData := make([][]int, n)
    for i := range costData {
        costData[i] = make([]int, 4)
    }
    return BusBooking{
        tot:      0,
        minTot:   0,
        costData: costData,
    }
}

func (this *BusBooking) Toggle(seat string) {
    i := 0
    for k := 1; k < len(seat); k++ {
        i = i*10 + int(seat[k]-'0')
    }
    i -= 1
    j := int(seat[0] - 'A')

    if this.costData[i][j] > 0 {
        this.minTot -= 1
        this.tot -= this.costData[i][j]
        this.costData[i][j] = 0
        return
    }

    cost := 1
    if (j == 0 && this.costData[i][1] > 0) || (j == 3 && this.costData[i][2] > 0) {
        cost = 3
    }
    this.minTot += 1
    this.tot += cost
    this.costData[i][j] = cost
}

func (this *BusBooking) GetTotalTime() int {
    return this.tot
}

func (this *BusBooking) GetMinTime() int {
    return this.minTot
}

/**
 * Your BusBooking object will be instantiated and called as such:
 * obj := Constructor(n);
 * obj.Toggle(seat);
 * param_2 := obj.GetTotalTime();
 * param_3 := obj.GetMinTime();
 */
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class BusBooking {
    private tot: number;
    private minTot: number;
    private costData: number[][];

    constructor(n: number) {
        this.tot = 0;
        this.minTot = 0;
        this.costData = Array.from({ length: n }, () => new Array<number>(4).fill(0));
    }

    toggle(seat: string): void {
        let i = 0;
        for (let k = 1; k < seat.length; k++) {
            i = i * 10 + (seat.charCodeAt(k) - '0'.charCodeAt(0));
        }
        i -= 1;
        const j = seat.charCodeAt(0) - 'A'.charCodeAt(0);

        if (this.costData[i][j] > 0) {
            this.minTot -= 1;
            this.tot -= this.costData[i][j];
            this.costData[i][j] = 0;
            return;
        }

        let cost = 1;
        if ((j === 0 && this.costData[i][1] > 0) || (j === 3 && this.costData[i][2] > 0)) {
            cost = 3;
        }
        this.minTot += 1;
        this.tot += cost;
        this.costData[i][j] = cost;
    }

    getTotalTime(): number {
        return this.tot;
    }

    getMinTime(): number {
        return this.minTot;
    }
}

/**
 * Your BusBooking object will be instantiated and called as such:
 * var obj = new BusBooking(n)
 * obj.toggle(seat)
 * var param_2 = obj.getTotalTime()
 * var param_3 = obj.getMinTime()
 */

Comments