Подсчёт текущего спроса на такси в заданной точке

Условие

Задача посвящена оценке текущего спроса на такси. Требуется реализовать функцию GetDemand, которая будет вычислять уровень спроса в указанной географической координате. Для этого необходимо собрать данные о поездках, разбивая их по минутным интервалам, и учитывать только активность за последние три минуты.

type Point struct {
  Lat float32
  Lng float32
}

type Location struct {
  UpperLeft  Point
  LowerRight Point
}

var locations = []Location{
  {
    UpperLeft: Point{
      Lat: 70,
      Lng: 70,
    },
    LowerRight: Point{
      Lat: 69,
      Lng: 69,
    },
  },
  {
    UpperLeft: Point{
      Lat: 69,
      Lng: 69,
    },
    LowerRight: Point{
      Lat: 68,
      Lng: 68,
    },
  },
}

func (p Point) WithinBounds(upperLeft Point, lowerRight Point) bool {
  // naive (not correct) realization
  if p.Lat > upperLeft.Lat {
    return false
  }
  if p.Lng > upperLeft.Lng {
    return false
  }
  if p.Lat < lowerRight.Lat {
    return false
  }
  if p.Lng < lowerRight.Lng {
    return false
  }
  return true
}

type Consumer struct{}

func (c *Consumer) ConsumeRider(ctx context.Context, points []Point) {
  for _, p := range points {
    for _, l := range locations {
      if p.WithinBounds(l.UpperLeft, l.LowerRight) {
        // point belongs to this location
      }
    }
    // what if we can not find location
  }
}

func (c *Consumer) ConsumeDriver(ctx context.Context, points []Point) {
  for _, p := range points {
    for _, l := range locations {
      if p.WithinBounds(l.UpperLeft, l.LowerRight) {
        // point belongs to this location
      }
    }
    // what if we can not find location
  }
}

func (c *Consumer) GetDemand(ctx context.Context, point Point) float64 {
  // TODO
  riders := 123
  drivers := 50
  return float64(riders) / float64(drivers)
}

Ответ

Храните для каждой зоны счётчики пассажирских и водительских событий по минутам. Спрос — их отношение за выбранное окно; поведение при нуле водителей и пересечении зон нужно определить явно.

Ниже окно — текущая и две предыдущие календарные минуты, время — момент приёма. Это не точные последние 180 секунд. Каждая точка считается отдельным событием: без ID нельзя посчитать уникальных активных людей или убрать повторы. Для заданных прямоугольников без пересечения 180-го меридиана используем обе границы независимо от порядка углов; в пересечении выбираем первую зону. Нужны context, math, sync, time и типы Point/Location/locations из условия:

type counts struct { riders, drivers int }
type Consumer struct {
    mu sync.Mutex
    buckets map[int]map[int64]counts
}
func between(v, a, b float32) bool {
    if a > b { a, b = b, a }
    return v >= a && v <= b
}
func region(p Point) int {
    for i, l := range locations {
        if between(p.Lat, l.UpperLeft.Lat, l.LowerRight.Lat) &&
           between(p.Lng, l.UpperLeft.Lng, l.LowerRight.Lng) {
            return i
        }
    }
    return -1
}
func (c *Consumer) prune(minute int64) {
    for id, buckets := range c.buckets {
        for stamp := range buckets {
            if stamp < minute-2 { delete(buckets, stamp) }
        }
        if len(buckets) == 0 { delete(c.buckets, id) }
    }
}
func (c *Consumer) record(ctx context.Context, points []Point, rider bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    now := time.Now().Unix()/60
    if c.buckets == nil { c.buckets = make(map[int]map[int64]counts) }
    c.prune(now)
    for _, p := range points {
        if ctx.Err() != nil { return }
        id := region(p)
        if id < 0 { continue }
        if c.buckets[id] == nil { c.buckets[id] = make(map[int64]counts) }
        n := c.buckets[id][now]
        if rider { n.riders++ } else { n.drivers++ }
        c.buckets[id][now] = n
    }
}
func (c *Consumer) ConsumeRider(ctx context.Context, points []Point) {
    c.record(ctx, points, true)
}
func (c *Consumer) ConsumeDriver(ctx context.Context, points []Point) {
    c.record(ctx, points, false)
}
func (c *Consumer) GetDemand(ctx context.Context, point Point) float64 {
    if ctx.Err() != nil { return math.NaN() }
    id := region(point)
    if id < 0 { return math.NaN() }
    c.mu.Lock()
    defer c.mu.Unlock()
    now := time.Now().Unix()/60
    c.prune(now)
    total := counts{}
    for stamp, n := range c.buckets[id] {
        if stamp >= now-2 && stamp <= now {
            total.riders += n.riders
            total.drivers += n.drivers
        }
    }
    if total.drivers == 0 {
        if total.riders == 0 { return 0 }
        return math.Inf(1)
    }
    return float64(total.riders)/float64(total.drivers)
}

Вне зон/при отмене возвращается NaN; при пассажирах без водителей — +Inf, при отсутствии обоих — 0. Для внешнего API лучше результат с error/status вместо специальных float. Для точного скользящего окна храните более мелкие бакеты или timestamps; для реального спроса — ID, статус и время события. Несколько экземпляров сервиса требуют общего состояния или маршрутизации по зоне.