package q2402

import (
	"container/heap"
	"slices"
)

type Room struct {
	id           int
	meetingStart int
	meetingEnd   int
}

type Rooms []Room

func (r *Rooms) Len() int          { return len(*r) }
func (r *Rooms) Push(x any)        { (*r) = append((*r), x.(Room)) }
func (r *Rooms) Swap(i int, j int) { (*r)[i], (*r)[j] = (*r)[j], (*r)[i] }

func (r *Rooms) Less(i int, j int) bool {
	if (*r)[i].meetingEnd == (*r)[j].meetingEnd {
		return (*r)[i].id < (*r)[j].id
	}
	return (*r)[i].meetingEnd < (*r)[j].meetingEnd
}

func (r *Rooms) Pop() any {
	last := len(*r) - 1
	ret := (*r)[last]
	*r = (*r)[:last]
	return ret
}

func mostBooked(n int, meetings [][]int) int {
	timesBooked := make([]int, n)
	empty := make(Rooms, n)
	for i := range empty {
		empty[i] = Room{id: i}
	}
	inUse := make(Rooms, 0, n)

	slices.SortFunc(meetings, func(a, b []int) int { return a[0] - b[0] })
	for i := range meetings {
		start, end := meetings[i][0], meetings[i][1]
		for len(inUse) > 0 && inUse[0].meetingEnd <= start {
			heap.Push(&empty, Room{id: inUse[0].id})
			heap.Pop(&inUse)
		}

		if len(empty) > 0 {
			id := empty[0].id
			timesBooked[id]++
			heap.Push(&inUse, Room{
				id:           id,
				meetingStart: start,
				meetingEnd:   end,
			})
			heap.Pop(&empty)
		} else {
			room := &inUse[0]
			timesBooked[room.id]++
			room.meetingStart, room.meetingEnd = room.meetingEnd, end-start+room.meetingEnd
			heap.Fix(&inUse, 0)
		}
	}

	mb, mbIdx := timesBooked[0], 0
	for i := 1; i < len(timesBooked); i++ {
		if timesBooked[i] > mb {
			mb, mbIdx = timesBooked[i], i
		}
	}
	return mbIdx
}

var _ heap.Interface = &Rooms{}
var _ = mostBooked