Go Coding with Asparagos: Saving Apples from Pies

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 = 5

  Output: true

  At 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 point 7.

  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 = 4

  Output: false

  At 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

1. First, we build a list of events: each trip creates a pick-up event at from and a drop-off event at to. 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), and isFrom (whether it is a pick-up or drop-off).

2. We iterate through the events and update the current number of apples on the train num. If it’s a drop-off, we subtract the size of the group from num. Otherwise, we add the group size to num.

3. If at any point a pick-up would exceed capacity, return false.
   Otherwise, return true.
   

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