40. Peak Concurrent Sessions per User Group

Origin: HackerRank Prep Kit #40

题目描述

给定一组事件，每个事件是 [timestamp, user_id, group_id, event_type]，event_type 为 “login” 或 “logout”。计算每个 group 的峰值并发会话数。返回 [group_id, peak_count] 数组。

示例

Example

Input:

events = [
  ['1', '101', '500', 'login'],
  ['2', '102', '500', 'login'],
  ['5', '101', '500', 'logout'],
  ['6', '102', '500', 'logout']
]

Output: [[500, 2]]

Explanation: group 500 在时间 2 时有两个并发会话（user 101 和 102 都在线），峰值 = 2。

Sample Input 0

2 4 1 101 500 login 2 101 500 logout

Output: 500 1

Sample Input 1

2 4 5 123 700 login 5 123 700 logout

Output: 700 1

约束

• 0 <= events.length <= 100000
• 0 <= timestamp <= 10
• 1 <= user_id <= 10
• 1 <= group_id <= 10
• event_type ∈ {“login”, “logout”}
• 事件可能未按时间戳排序
• 多个事件可能共享同一时间戳
• 用户可在不同 group 有重叠会话
• 每个 logout 都有对应的 login

关键信息

• 按时间排序后，login +1，logout -1，维护每个 group 的当前计数
• 同一时间戳：logout 优先于 login？还是 login 优先？需要确认
• 返回每个 group 的峰值

Resolution

我的解法

function computeGroupPeakConcurrency(events: string[][]): number[][] {
    if (!events.length) return []
 
    const groupMap = new Map()
    const groupMaxMap = new Map()
    const parsed = events.map(e => ({
        timestamp: Number(e[0]),
        userId: e[1],
        groupId: Number(e[2]),
        event: e[3]
    }))
 
    parsed.sort((a, b) => {
        const timeDiff = a.timestamp - b.timestamp
        if (timeDiff !== 0) return timeDiff
        return a.event === 'login' ? -1 : 1
    })
    for (let i = 0; i < parsed.length; i++) {
        const { groupId, event } = parsed[i]
        if (!groupMap.has(groupId)) {
            groupMap.set(groupId, 0)
            groupMaxMap.set(groupId, groupMap.get(groupId))
        }
        if (event === 'login') {
            groupMap.set(groupId, groupMap.get(groupId) + 1)
            groupMaxMap.set(groupId, Math.max(groupMaxMap.get(groupId), groupMap.get(groupId)))
        } else {
            groupMap.set(groupId, groupMap.get(groupId) - 1)
        }
    }
    const result: number[][] = []
    for (const [key, value] of groupMaxMap) {
        result.push([key, value])
    }
    return result.sort((a, b) => Number(a[0]) - Number(b[0]))
}

解题思路

扫描线问题。三步走：

1. 把字符串字段转成 number（groupId 必须转，否则 Map key 和输出类型不对）
2. 按时间戳排序，同一时间戳 login 优先（login 排在 logout 前面）
3. 遍历事件，login +1，logout -1，记录每个 group 的峰值

踩坑

• 字符串 vs 数字：groupId 没转 number，Map 用字符串做 key，输出也是字符串，HackerRank 期望数字类型。这是最大的 bug。
• 同一时间戳排序方向：login 优先（login 排在 logout 前面），否则同一时刻的 logout 先处理会虚低
• groupMap 初始化：第一次遇到 groupId 时要先初始化为 0，不能只在 login 时初始化
• truthy 判断：count 为 0 时是 falsy，不能用 if (groupMap.get(groupId)) 判断，必须用 has()
• 题目和用例不一致：题目说 “output order does not matter” 但实际必须按 group_id 排序；说 “每个 logout 有对应 login” 但用例里出现了无对应 login 的 logout。遇到先 logout 的 group，count 记 -1 但 peak 记 0（不减成负数）

复杂度

• 时间：O(n log n)，排序
• 空间：O(n)，Map 存储