题

1450. 在既定时间做作业的学生人数

给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。

已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。

请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。

示例 1：
输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出：1
解释：一共有 3 名学生。
第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。
第三名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。
提示：

startTime.length == endTime.length 1 <= startTime.length <= 100 1 <= startTime[i] <= endTime[i] <= 1000 1 <= queryTime <= 1000

析

区间内加减操作，有很多解题思路，差分、树状数组、线段树。本题还可以使用暴力、二分等算法实现，全鱼宴了属于是。

解

暴力

 func busyStudent(startTime []int, endTime []int, queryTime int) int {
    ans := 0
    for i := range startTime {
        if startTime[i] <= queryTime && endTime[i] >= queryTime {
            ans++
        }
    }
    return ans
 }

二分

func BisectLeft(arr []int, target int) int {
    l, r := 0, len(arr)
    for l < r {
        m := l + (r-l)>>1
        if arr[m] >= target {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}
func BisectRight(arr []int, target int) int {
    l, r := 0, len(arr)
    for l < r {
        m := l + (r-l)>>1
        if arr[m] <= target {
            l = m + 1
        } else {
            r = m
        }
    }
    return l
}

func busyStudent(startTime []int, endTime []int, queryTime int) int {
    // 主体思想是拿查询时间之前（包含查询时间）开始的学生数量x，减去查询时间之前(不包含查询时间)结束的学生数量y
    // 得到的就是查询时间点在做作业的人数
    sort.Ints(startTime)
    sort.Ints(endTime)
    return BisectRight(startTime, queryTime) - BisectLeft(endTime, queryTime)
}

差分

func busyStudent(startTime []int, endTime []int, queryTime int) int {
	maxTime := 0
	// 确定最大时刻
	for _, v := range endTime {
		if v > maxTime {
			maxTime = v
		}
	}

	// 差分数组
	cnt := make([]int, maxTime+2)
	for i := range startTime {
		// 在开始时刻加1
		cnt[startTime[i]] += 1
		// 在结束的后一时刻减1
		cnt[endTime[i]+1] -= 1
	}

	// 累加变量
	sum := 0
	for i, v := range cnt {
		sum += v
		// 一直查询直到指定时刻
		if i >= queryTime {
			break
		}
	}
	return sum
}

树状数组

const Max = 1005
type BitTree struct {
    arr []int
}

func lowbit(x int) int {
    return x & (-x)
}

func (bt *BitTree) Add(pos int, delta int) {
    pos += 1
    for ; pos < Max; pos += lowbit(pos) {
        bt.arr[pos] += delta
    }
}

func (bt *BitTree) Sum(pos int) int {
    pos += 1
    sum := 0
    for ; pos > 0; pos -= lowbit(pos) {
        sum += bt.arr[pos]
    }
    return sum
}

func busyStudent(startTime []int, endTime []int, queryTime int) int {
    bt := &BitTree{make([]int, Max)}

    for i := range startTime {
        bt.Add(startTime[i], 1)
        bt.Add(endTime[i]+1, -1)
    }

    return bt.Sum(queryTime)
}

线段树


type Node struct {
	l   *Node
	r   *Node
	val int
	add int
}

// 下推标记
func (n *Node) PushDown(lCnt, rCnt int) {
	if n.l == nil {
		n.l = &Node{}
	}
	if n.r == nil {
		n.r = &Node{}
	}
	if n.add == 0 {
		return
	}
	n.l.val += lCnt * n.add
	n.r.val += rCnt * n.add
	n.l.add += n.add
	n.r.add += n.add
	n.add = 0
}

// 数据汇聚
func (n *Node) PushUp() {
	n.val = n.l.val + n.r.val
}

func (n *Node) _update(l, r int, s, e int, delta int) {
	if s >= l && e <= r {
		n.val += delta * (e - s + 1)
		n.add += delta
		return
	}
	m := s + (e-s)>>1
	n.PushDown(m-s+1, e-m)
	if l <= m {
		n.l._update(l, r, s, m, delta)
	}
	if r > m {
		n.r._update(l, r, m+1, e, delta)
	}
	n.PushUp()
}

func (n *Node) Update(l, r int, delta int) {
	n._update(l, r, 0, int(1e9), delta)
}

func (n *Node) _range(l, r int, s, e int) int {
	if s >= l && e <= r {
		return n.val
	}
	m := s + (e-s)>>1
	n.PushDown(m-s+1, e-m)
	sum := 0
	if l <= m {
		sum += n.l._range(l, r, s, m)
	}
	if r > m {
		sum += n.r._range(l, r, m+1, e)
	}
	return sum
}

func (n *Node) Range(l, r int) int {
	return n._range(l, r, 0, int(1e9))
}

func busyStudent(startTime []int, endTime []int, queryTime int) int {
	st := &Node{}
	for i := range startTime {
		st.Update(startTime[i], endTime[i], 1)
	}
	return st.Range(queryTime, queryTime)
}

最后修改于 2022-08-22