Input:
cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
There are 4 stations and cost[i][j] indicates cost to reach j
from i. The entries where j < i are meaningless.
Output:
The minimum cost is 65
The minimum cost can be obtained by first going to station 1
from 0. Then from station 1 to station 3.
1
2
3
| abstract class Vehicle { } |
1
2
3
| class Motorcycle extends Vehicle{ } |
1
2
3
| class Car extends Vehicle { } |
1
2
3
| class Bus extends Vehicle { } |
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
| abstract class Slot { private boolean isOccupied; private int slotNumber; Slot(int slotNumber) { isOccupied = false; this.slotNumber = slotNumber; } boolean isOccupied() { return isOccupied; } int getSlotNumber() { return slotNumber; } void park() { isOccupied = true; } void unPark() { isOccupied = false; } @Override public boolean equals(Object o) { return (((Slot) o).slotNumber == this.slotNumber); } @Override public int hashCode() { int hash = 5; hash = 53 * hash + this.slotNumber; return hash; } } |
1
2
3
4
5
6
| class SmallSlot extends Slot { SmallSlot(int slotNumber){ super(slotNumber); }} |
1
2
3
4
5
6
| class CompactSlot extends Slot { CompactSlot(int slotNumber) { super(slotNumber); }} |
1
2
3
4
5
6
| class LargeSlot extends Slot { LargeSlot(int slotNumber) { super(slotNumber); } } |
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| public class ParkingLot { private static final int NUMBER_OF_SMALL_SLOTS = 10; private static final int NUMBER_OF_COMPACT_SLOTS = 10; private static final int NUMBER_OF_LARGE_SLOTS = 10; public Map<Long, Slot> occupiedSlots; private List<Slot> smallSlots; private List<Slot> compactSlots; private List<Slot> largeSlots; public ParkingLot() { smallSlots = new ArrayList<>(NUMBER_OF_SMALL_SLOTS); compactSlots = new ArrayList<>(NUMBER_OF_COMPACT_SLOTS); largeSlots = new ArrayList<>(NUMBER_OF_LARGE_SLOTS); createSlots(); occupiedSlots = new HashMap<>(); } private void createSlots() { for (int i = 1; i <= NUMBER_OF_SMALL_SLOTS; i++) { smallSlots.add(new SmallSlot(i)); } for (int i = 1; i <= NUMBER_OF_COMPACT_SLOTS; i++) { compactSlots.add(new CompactSlot(i)); } for (int i = 1; i <= NUMBER_OF_LARGE_SLOTS; i++) { largeSlots.add(new LargeSlot(i)); } } public long park(Vehicle vehicle) { Slot slot; long uniqueToken = -1; if (vehicle instanceof Motorcycle) { if ((slot = getFirstEmptySlot(smallSlots)) != null) { uniqueToken = parkHelper(slot, vehicle); } else if ((slot = getFirstEmptySlot(compactSlots)) != null) { uniqueToken = parkHelper(slot, vehicle); } else if ((slot = getFirstEmptySlot(largeSlots)) != null) { uniqueToken = parkHelper(slot, vehicle); } } else if (vehicle instanceof Car) { if ((slot = getFirstEmptySlot(compactSlots)) != null) { uniqueToken = parkHelper(slot, vehicle); } else if ((slot = getFirstEmptySlot(largeSlots)) != null) { uniqueToken = parkHelper(slot, vehicle); } } else { if ((slot = getFirstEmptySlot(largeSlots)) != null) { uniqueToken = parkHelper(slot, vehicle); } } return uniqueToken; } public void unPark(long uniqueToken) { occupiedSlots.get(uniqueToken).unPark(); occupiedSlots.remove(uniqueToken); } private Slot getFirstEmptySlot(List<Slot> slots) { Iterator<Slot> slotIterator = slots.iterator(); boolean isSlotFound = false; Slot emptySlot = null; while (slotIterator.hasNext() && !isSlotFound) { emptySlot = slotIterator.next(); if (!emptySlot.isOccupied()) { isSlotFound = true; } } return emptySlot; } private long parkHelper(Slot slot, Vehicle vehicle) { slot.park(); long uniqueToken = vehicle.hashCode() * 43; occupiedSlots.put(uniqueToken, slot); return uniqueToken; }} |