Go solution Sort and Slide Window
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
}
Comments (0)