【Golang, TypeScript】期間の重複をマージする

Feb 23, 2023

はじめに

業務で期間の範囲を扱う際に、範囲の重複を考慮する必要がありました。

例として、以下のように範囲の重複があった場合、

gantt
dateFormat YYYY-MM-DDTHH:mm:ssZ
axisFormat %m/%d %H:%M
title　期間
section 範囲
A : des1, 2023-01-10T00:00:00Z, 9h
B : des2, 2023-01-10T06:00:00Z, 7h
C : des2, 2023-01-10T03:00:00Z, 2h
D : des2, 2023-01-10T18:00:00Z, 2h

最終的に以下のような期間の重複している範囲をマージした結果を求めているイメージです。

gantt
dateFormat  YYYY-MM-DDTHH:mm:ssZ
axisFormat %m/%d %H:%M

section 範囲
X : des1, 2023-01-10T00:00:00Z, 13h
Y : des1, 2023-01-10T18:00:00Z, 2h

成果物

https://github.com/kntks/blog-code/tree/main/2023/02/merge-overlapping-inteval

TypeScript コード

まずはコードです。
重複する間隔のマージを参考にTypeScriptで書いてみました。

const intervals = [
  {start: new Date("2023-01-10T00:00:00Z"), end: new Date("2023-01-10T09:00:00Z")},
  {start: new Date("2023-01-10T06:00:00Z"), end: new Date("2023-01-10T13:00:00Z")},
  {start: new Date("2023-01-10T03:00:00Z"), end: new Date("2023-01-10T05:00:00Z")},
  {start: new Date("2023-01-10T18:00:00Z"), end: new Date("2023-01-10T20:00:00Z")},
]

function mergeInterval(intervals: {start: Date, end: Date}[]) {
  const stack: {start: Date, end: Date}[] = []
  intervals
      .map((x) => ({...x}))
      .sort((x, y) => x.start.getTime() - y.start.getTime())
      .forEach((curr) => {
          const top = stack[stack.length -1]
          if(!top || top.end < curr.start) {
              stack.push(curr)
              return
          }
          if(top.end < curr.end) top.end = curr.end
      })

 return stack
}

console.log(mergeInterval(intervals))

意図した結果になっていそうです！

$ npx ts-node index.ts
[
  { start: 2023-01-10T00:00:00.000Z, end: 2023-01-10T13:00:00.000Z },
  { start: 2023-01-10T18:00:00.000Z, end: 2023-01-10T20:00:00.000Z }
]

TypeScript playground

簡単に解説

はじめにArray.prototype.map()を使ってintervalsから新しい配列を生成します。

intervals.map((x) => ({...x}))

理由は、後ろに続くArray.prototype.sort()が元の配列の順序を変えてしまうからです。

ソートされた元の配列への参照です。なお、配列はその場でソートされ、コピーは作成されません。
返値

続いてforEachの中を見てみます。

.forEach((curr) => {
      const top = stack[stack.length -1]
      if(!top || top.end < curr.start) {
          stack.push(curr)
          return
      }
      if(top.end < curr.end) top.end = curr.end
  })

ここのifの条件ですが

if(!top || top.end < curr.start)

配列stackにデータをpushしても良い条件は、以下の通りです。

• 配列が空である
• 比較対象期間の始まりの時間（curr.start）が、stack内にある一番遅い時間（top.end）よりも後ろにある

つまり、期間が重複していなければpushしてもいいよね、ということです。図で表すと以下になります。

gantt
dateFormat  YYYY-MM-DDTHH:mm:ssZ
axisFormat %m/%d %H:%M
title　期間

section 範囲
stack最後の期間(top) : des1, 2023-01-10T00:00:00Z, 30m
比較対象(curr) : des2, 2023-01-10T01:45:00Z, 15m

最後の条件です。

if(top.end < curr.end) top.end = curr.end

処理がここまで到達しているということは、stack内の一番最後の期間（top）と比較対象の期間（curr）が重複することがわかっています。
最後の条件では、比較対象の期間はstack内の一番最後の期間（top）内なのかを確認しています。

図で表すと以下のどちらなのかを判定している、ということになります。

gantt
dateFormat  YYYY-MM-DDTHH:mm:ssZ
axisFormat %m/%d %H:%M
title　期間

section 重複している
stack最後の期間(top) : des1, 2023-01-10T00:00:00Z, 30m
比較対象(curr) : des2, 2023-01-10T00:20:00Z, 20m

gantt
dateFormat  YYYY-MM-DDTHH:mm:ssZ
axisFormat %m/%d %H:%M
title　期間

section 期間内
stack最後の期間(top) : des1, 2023-01-10T00:00:00Z, 30m
比較対象(curr) : des2, 2023-01-10T00:05:00Z, 20m

比較対象期間の最後の時間（curr.end）がstack内の一番遅い時間（top.end）も後ろにある場合は、top.endを更新して終わりです。

Go言語 コード

Go言語でも実装してみました。先ほどのTypeScriptのときと処理は同じです。

type Interval struct {
  Start time.Time
  End   time.Time
}

func main() {
  local := time.FixedZone("Asia/Tokyo", 9*60*60)

  intervals := []Interval{
    {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 9, 0, 0, 0, local)},
    {Start: time.Date(2023, 1, 10, 6, 0, 0, 0, local), End: time.Date(2023, 1, 10, 13, 0, 0, 0, local)},
    {Start: time.Date(2023, 1, 10, 3, 0, 0, 0, local), End: time.Date(2023, 1, 10, 5, 0, 0, 0, local)},
    {Start: time.Date(2023, 1, 10, 18, 0, 0, 0, local), End: time.Date(2023, 1, 10, 20, 0, 0, 0, local)},
  }

  for _, interval := range mergeIntervals(intervals) {
    fmt.Println(interval)
  }
}

func mergeIntervals(intervals []Interval) []Interval {
  copied := make([]Interval, len(intervals))
  copy(copied, intervals)
  sort.Slice(copied, func(i, j int) bool { return intervals[i].Start.Before(intervals[j].Start) })

  l := list.New()
  for _, curr := range copied {
    top := l.Back()
    if top == nil || top.Value.(Interval).End.Before(curr.Start) {
      l.PushBack(curr)
      continue
    }
    if top.Value.(Interval).End.Before(curr.End) {
      merged := top.Value.(Interval)
      merged.End = curr.End
      l.Remove(top)
      l.PushBack(merged)
    }
  }

  results := make([]Interval, 0, l.Len())
  for e := l.Front(); e != nil; e = e.Next() {
    results = append(results, e.Value.(Interval))
  }
  return results
}

$ go run main.go
{2023-01-10 00:00:00 +0900 Asia/Tokyo 2023-01-10 13:00:00 +0900 Asia/Tokyo}
{2023-01-10 18:00:00 +0900 Asia/Tokyo 2023-01-10 20:00:00 +0900 Asia/Tokyo}

playground

Go言語の場合は、time.Beforeの境界の挙動が怪しかったので、テストを書いて動作を確認しました。

func Test_mergeIntervals(t *testing.T) {

  local := time.FixedZone("Asia/Tokyo", 9*60*60)

  type args struct {
    intervals []Interval
  }
  tests := []struct {
    name string
    args args
    want []Interval
  }{
    {
      name: "期間が重複していないとき、マージされない",
      args: args{
        intervals: []Interval{
          {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 1, 0, 0, 0, local)},
          {Start: time.Date(2023, 1, 10, 2, 0, 0, 0, local), End: time.Date(2023, 1, 10, 3, 0, 0, 0, local)},
        },
      },
      want: []Interval{
        {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 1, 0, 0, 0, local)},
        {Start: time.Date(2023, 1, 10, 2, 0, 0, 0, local), End: time.Date(2023, 1, 10, 3, 0, 0, 0, local)},
      },
    },
    {
      name: "期間が重複しているとき、マージされる",
      args: args{
        intervals: []Interval{
          {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 9, 0, 0, 0, local)},
          {Start: time.Date(2023, 1, 10, 6, 0, 0, 0, local), End: time.Date(2023, 1, 10, 13, 0, 0, 0, local)},
        },
      },
      want: []Interval{
        {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 13, 0, 0, 0, local)},
      },
    },
    {
      name: "1つ目の終了時間と二つ目の開始時間が同じとき、マージされる",
      args: args{
        intervals: []Interval{
          {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 9, 0, 0, 0, local)},
          {Start: time.Date(2023, 1, 10, 9, 0, 0, 0, local), End: time.Date(2023, 1, 10, 13, 0, 0, 0, local)},
        },
      },
      want: []Interval{
        {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 13, 0, 0, 0, local)},
      },
    },
    {
      name: "二つ目の期間が1つ目の期間内のとき、マージされる",
      args: args{
        intervals: []Interval{
          {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 9, 0, 0, 0, local)},
          {Start: time.Date(2023, 1, 10, 1, 0, 0, 0, local), End: time.Date(2023, 1, 10, 5, 0, 0, 0, local)},
        },
      },
      want: []Interval{
        {Start: time.Date(2023, 1, 10, 0, 0, 0, 0, local), End: time.Date(2023, 1, 10, 9, 0, 0, 0, local)},
      },
    },
  }

  for _, tt := range tests {
    t.Run(tt.name, func(t *testing.T) {
      got := mergeIntervals(tt.args.intervals)
      if diff := cmp.Diff(tt.want, got); diff != "" {
        t.Errorf("mergeIntervals() mismatch (-want +got):\n%s", diff)
      }
    })
  }
}

まとめ

重複する期間のマージをTypeScript、Golangで実装しました。
今回作成したコードはkntks/blog-code/merge-overlapping-inteval - GitHubにあります。

参考になれば幸いです。

参考

• 重複する間隔のマージ
• container/list - Go Packages
• time - Go Packages
• sort - Go Packages

Tags:

• Golang
• TypeScript

Cloudflare Pages + Terraformでブログ環境を構築する

【M1 Mac】lima + DockerでMySQLを起動する