package main

import (
	"sort"
)

// uncovered calculates how much of the parent range is not covered by at least
// one of the ranges that its children cover.
func uncovered(parent [2]int64, children ...[2]int64) int64 {
	var uncovered int64

	sorted := append([][2]int64(nil), children...)
	sort.Slice(sorted, func(i, j int) bool { return sorted[i][0] < sorted[j][0] })

	now := parent[0]
	parentEnd := parent[1]
	for _, child := range sorted {
		childStart := child[0]
		childEnd := child[1]
		if parentEnd < now {
			// The progress marker starts beyond the end of the parent; because
			// the list is sorted, we know we're done.
			break
		}
		if parentEnd < childStart {
			// This child starts beyond the end of the parent; because the list
			// is sorted, we know we're done.
			break
		}
		if now <= childStart {
			// This child starts after a gap in coverage. Calculate the
			// uncovered time.
			uncovered += childStart - now
		}
		if now <= childEnd {
			// This child overlaps with an earlier child, and extends the
			// coverage area.
			now = childEnd
		}
	}

	if now < parentEnd {
		// Mark the tail end of the parent as uncovered.
		uncovered += parentEnd - now
	}

	return uncovered
}

// waterfall calculates the largest possible number of waterfall steps that this
// parent's children could describe.
func waterfall(parent [2]int64, children ...[2]int64) int {
	waterfall := 0

	sorted := append([][2]int64(nil), children...)
	sort.Slice(sorted, func(i, j int) bool { return sorted[i][0] < sorted[j][0] })

	now := parent[0]
	parentEnd := parent[1]
	for _, child := range sorted {
		childStart := child[0]
		childEnd := child[1]

		if parentEnd <= childStart {
			// No time left for a child to start and end before the parent ends.
			break
		}

		if now <= childStart {
			// We've reached a new step / generation.
			waterfall++
			now = childEnd
		}

		if childEnd < now {
			// The current generation ends earlier than expected.
			now = childEnd
		}
	}

	if parentEnd < now {
		// The current generation didn't before the parent. Take it back
		waterfall--
	}

	return waterfall
}
