LeetCode每日一题解析：两个最好的不重叠活动

LeetCode每日一题解析：两个最好的不重叠活动

在LeetCode上，我们经常遇到各种算法和逻辑问题。今天，我们将解析题目编号2054，即“两个最好的不重叠活动”。这个问题要求我们在给定的活动中找出两个不重叠且价值最大的活动。

题目理解

首先，我们需要明确题目的要求。题目中提到的是“你最多可以参加两个时间不重叠活动”，这意味着我们需要从多个活动中选择两个活动，这两个活动的时间段不能重叠，并且它们的总价值需要是最大的。

解题思路

为了解决这个问题，我们可以采用以下步骤：

1. 排序：首先，我们将活动按照开始时间和结束时间分别进行排序。这样可以方便我们后续的遍历和比较。
2. 双指针法：使用两个指针，一个指向开始时间排序后的活动（记为e1），另一个指向结束时间排序后的活动（记为e2）。
3. 遍历与比较：通过遍历e2数组，对于每个活动，我们寻找e1中不与之重叠的活动，并计算它们的总价值，尝试更新最大价值。
4. 更新最大价值：在遍历过程中，我们需要不断更新遇到的最大价值，并在最后返回这个最大价值作为结果。

代码实现

以下是该算法的Java代码实现：

public int maxTwoEvents(int events) {
    int n = events.length;
    int eventsByEnd = Arrays.copyOf(events, n);
    Arrays.sort(eventsByEnd, Comparator.comparingInt(a -> a[1]));
    Arrays.sort(events, Comparator.comparingInt(a -> a[0]));
    int l = 0, r = 0;
    int lMax = 0;
    int ans = 0;
    while (l < n) {
        while (r < n && events[r][0] <= eventsByEnd[l][1]) {
            ans = Math.max(ans, lMax + events[r][2]);
            r++;
        }
        lMax = Math.max(lMax, eventsByEnd[l][2]);
        l++;
    }
    ans = Math.max(ans, lMax);
    return ans;
}

总结

通过上述步骤和代码实现，我们可以有效地找出两个不重叠且价值最大的活动。这种方法利用了排序和双指针法，使得算法的时间复杂度得到了有效控制。在解决类似问题时，我们可以借鉴这种思路，灵活运用各种算法技巧来优化我们的解决方案。