Java/Kotlin中高效查找时间重叠事件的最优实现方案

核心思路 #

要满足O(logn)查询复杂度且低GC开销，区间树是正确方向，但需针对GC问题做针对性优化——核心是避免频繁创建临时对象，复用已有集合/结构；静态数据场景下，排序+二分查找结合后缀最大值优化也是高效且低GC的选择。

优化版区间树实现（支持动态数据） #

定义区间对象 #

Kotlin

data class Interval(val id: String, val start: Long, val end: Long)

Java

public class Interval {
    private final String id;
    private final long start;
    private final long end;

    public Interval(String id, long start, long end) {
        this.id = id;
        this.start = start;
        this.end = end;
    }

    public String getId() { return id; }
    public long getStart() { return start; }
    public long getEnd() { return end; }
}

区间树实现（低GC优化） #

通过复用结果集合、预计算节点最大end值来减少临时对象创建：

Kotlin实现

class IntervalTree(private val intervals: List<Interval>) {
    private val root: Node?

    init {
        root = buildTree(intervals.sortedBy { it.start })
    }

    private class Node(val interval: Interval, val maxEnd: Long, val left: Node?, val right: Node?)

    private fun buildTree(sortedIntervals: List<Interval>): Node? {
        if (sortedIntervals.isEmpty()) return null
        val mid = sortedIntervals.size / 2
        val midInterval = sortedIntervals[mid]
        val left = buildTree(sortedIntervals.subList(0, mid))
        val right = buildTree(sortedIntervals.subList(mid + 1, sortedIntervals.size))
        val maxEnd = maxOf(
            midInterval.end,
            left?.maxEnd ?: Long.MIN_VALUE,
            right?.maxEnd ?: Long.MIN_VALUE
        )
        return Node(midInterval, maxEnd, left, right)
    }

    // 复用传入的结果列表，避免频繁创建新集合
    fun query(target: Long, result: MutableList<Interval>) {
        result.clear()
        query(root, target, result)
    }

    private fun query(node: Node?, target: Long, result: MutableList<Interval>) {
        if (node == null) return
        // 当前区间包含目标值，加入结果
        if (node.interval.start <= target && target <= node.interval.end) {
            result.add(node.interval)
        }
        // 左子树可能存在符合条件的区间
        if (node.left != null && node.left.maxEnd >= target) {
            query(node.left, target, result)
        }
        // 右子树可能存在符合条件的区间
        if (node.right != null && node.right.interval.start <= target) {
            query(node.right, target, result)
        }
    }

    // 迭代版实现，避免递归栈溢出，进一步优化性能
    fun queryIterative(target: Long, result: MutableList<Interval>) {
        result.clear()
        val stack = ArrayDeque<Node>()
        root?.let { stack.push(it) }
        while (stack.isNotEmpty()) {
            val node = stack.pop()
            if (node.interval.start <= target && target <= node.interval.end) {
                result.add(node.interval)
            }
            // 先压右节点，保证左节点优先处理
            if (node.right != null && node.right.interval.start <= target) {
                stack.push(node.right)
            }
            if (node.left != null && node.left.maxEnd >= target) {
                stack.push(node.left)
            }
        }
    }
}

关键GC优化点 #

• 复用结果集合：要求调用方传入可变列表，查询前清空再添加，避免每次创建新List对象。
• 预计算maxEnd：节点存储子树最大end值，避免查询时重复计算，减少临时变量。
• 迭代替代递归：避免递归带来的栈帧开销，同时降低潜在的内存波动。

静态数据场景：排序+二分查找方案 #

如果区间不会动态增删，该方案实现简单、GC开销极低，查询效率接近O(logn)：

Kotlin实现

class StaticIntervalQuery(sortedIntervals: List<Interval>) {
    private val sortedIntervals: List<Interval>
    private val suffixMaxEnd: LongArray

    init {
        this.sortedIntervals = sortedIntervals.sortedBy { it.start }
        this.suffixMaxEnd = LongArray(this.sortedIntervals.size).apply {
            if (isEmpty()) return@apply
            this[this.sortedIntervals.size - 1] = this@sortedIntervals.last().end
            for (i in this.sortedIntervals.size - 2 downTo 0) {
                this[i] = maxOf(this@sortedIntervals[i].end, this[i + 1])
            }
        }
    }

    fun query(target: Long, result: MutableList<Interval>) {
        result.clear()
        // 二分找到最大的start<=target的区间索引
        var left = 0
        var right = sortedIntervals.size - 1
        var maxIdx = -1
        while (left <= right) {
            val mid = (left + right) / 2
            if (sortedIntervals[mid].start <= target) {
                maxIdx = mid
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        if (maxIdx == -1) return
        // 遍历筛选，利用后缀maxEnd提前终止
        for (i in 0..maxIdx) {
            if (suffixMaxEnd[i] < target) break
            if (sortedIntervals[i].end >= target) {
                result.add(sortedIntervals[i])
            }
        }
    }
}

方案选择建议 #

• 动态数据（需增删区间）：使用优化版区间树，迭代实现优先，保证O(logn)查询复杂度与低GC开销。
• 静态数据：选择排序+二分查找方案，实现简单、性能稳定、GC压力极小。

内容的提问来源于stack exchange，提问作者Uriel Frankel