func maximumWhiteTiles(tiles [][]int, carpetLen int) (retResult int) {
if len(tiles) == 0 {
return retResult
}
// sort the tiles
sort.Slice(tiles, func(i, j int) bool {
if tiles[i][0] == tiles[j][0] {
return tiles[i][1] < tiles[j][1]
}
return tiles[i][0] < tiles[j][0]
})
// fmt.Printf("tiles:%+v \n", tiles)
tilesNum := len(tiles)
tilesCursor := 0
tilesWindow := make([][]int, 0, tilesNum)
tilesLenOfWindow := 0
for {
if tilesCursor >= tilesNum {
break
}
windowSize := len(tilesWindow)
currStartIdx := tiles[tilesCursor][0]
currEndIdx := tiles[tilesCursor][1]
windowHeadStartIdx := currStartIdx
windowHeadEndIdx := currEndIdx
if windowSize > 0 {
windowHeadStartIdx = tilesWindow[0][0]
windowHeadEndIdx = tilesWindow[0][1]
}
windowHeadSlots := windowHeadEndIdx - windowHeadStartIdx + 1
newWindowSlots := currEndIdx - windowHeadStartIdx + 1
if newWindowSlots > carpetLen {
if windowSize > 0 {
if newWindowSlots-windowHeadSlots > carpetLen {
tilesWindow = tilesWindow[1:]
// decrease tilesLenOfWindow
tilesLenOfWindow -= windowHeadSlots
} else {
// update window head
tilesWindow[0][0] = windowHeadStartIdx + newWindowSlots - carpetLen
// decrease tilesLenOfWindow
tilesLenOfWindow -= newWindowSlots - carpetLen
}
continue
} else {
// this tile is too long
// skip and clear the current window
tilesWindow = tilesWindow[:0]
tilesLenOfWindow = 0
tilesCursor += 1
continue
}
}
// increase tilesLenOfWindow
tilesLenOfWindow += currEndIdx - currStartIdx + 1
tilesWindow = append(tilesWindow, tiles[tilesCursor])
tilesCursor += 1
// update result
if tilesLenOfWindow > retResult {
// fmt.Printf("tilesLenOfWindow:%+v, tilesWindow:%+v\n", tilesLenOfWindow, tilesWindow)
retResult = tilesLenOfWindow
}
}
return retResult
}