This content originally appeared on DEV Community and was authored by Asparagos
Can a single train save apples from the pie threat?
Hi! I'm Asparagos - an asparagus who codes in Go. Here you’ll find everyday problems that a typical veggie might struggle with — and my Go solutions to them. Today we are solving the problem of Apple Escape 🍎.
Problem
The season of Apple Pies has begun. All the apples are leaving their homes in search of a safer place. Nobody wants to end up in a pie anymore — it’s just not trendy. A smoothie is better, or at least a strudel.
There is a train going in one direction with a limited number of seats. Apples travel in groups: each group wants to board the train at point X and leave at point Y.
Can the train take every apple without exceeding its seats?
Input 🍐
trips []Trip - information about group trips. Each Trip has a start point from, an end point to, and the group size num.
capacity int - the number of seats on the train.
Output 🍊
true if the train can carry all apples without exceeding capacity at any point; false otherwise.
Examples 🍋:
-
Example 1
Input:
trips = {{from: 2, to: 7, num: 1}, {from: 0, to: 2, num: 3}, {from: 1, to: 3, num: 2}}, capacity = 5Output:
trueAt point
0, the train takes 3 apples.Then, at point
1, it takes 2 more apples, so now all 5 seats are occupied.At point
2, 3 apples leave the train. At the same time, 1 apple boards the train. Now there are 3 apples on board.At point
3, 2 apples leave the train. Only 1 apple remains, which will leave at point7.The apples on board never exceeded the train’s capacity.
-
Example 2
Input:
trips = {{from: 0, to: 2, num: 3}, {from: 1, to: 3, num: 2}}, capacity = 4Output:
falseAt point
0, the train takes 3 apples.At point
1, it should take 2 more apples. That would require 5 seats, but the capacity is 4, so the train can't take them.
Solution 💡
First, we build a list of events: each trip creates a pick-up event at
fromand a drop-off event atto. We sort events by location in ascending order. When two events have the same location, put drop-offs before pick-ups. In this case, the freed seats can be reused immediately. Each event contains:location,num(group size), andisFrom(whether it is a pick-up or drop-off).We iterate through the
eventsand update the current number of apples on the trainnum. If it's a drop-off, we subtract the size of the group fromnum. Otherwise, we add the group size tonum.If at any point a pick-up would exceed capacity, return
false.
Otherwise, returntrue.
type Trip struct {
from int
to int
num int
}
type Event struct {
location int
num int
isFrom bool
}
func canSaveAllApples(trips []Trip, capacity int) bool {
events := make([]Event, 0, 2*len(trips))
for _, trip := range trips {
events = append(events, Event{trip.from, trip.num, true}, Event{trip.to, trip.num, false})
}
slices.SortFunc(events, func(a, b Event) int {
if a.location != b.location {
return cmp.Compare(a.location, b.location)
}
if a.isFrom == b.isFrom {
return 0
}
if !a.isFrom {
return -1
}
return 1
})
num := 0
for _, event := range events {
if !event.isFrom {
num -= event.num
continue
}
if capacity-num < event.num {
return false
}
num += event.num
}
return true
}
Feel free to check out the full code with tests on GitHub, and don’t hesitate to leave a ⭐ if you find it helpful!
This content originally appeared on DEV Community and was authored by Asparagos
Asparagos | Sciencx (2025-09-24T08:13:34+00:00) Go Coding with Asparagos: Saving Apples from Pies. Retrieved from https://www.scien.cx/2025/09/24/go-coding-with-asparagos-saving-apples-from-pies/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.