方法一：暴力

观察数据范围注意到矩阵大小不会超过 $100*100=10^4$，所以我们可以遍历矩阵所有数，统计负数的个数。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        for (int x : grid) {
            for (int y : x) {
                if (y < 0) {
                    num++;
                }
            }
        }
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        for (int[] row : grid) {
            for (int value : row) {
                if (value < 0) {
                    num++;
                }
            }
        }
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        foreach (int[] row in grid) {
            foreach (int value in row) {
                if (value < 0) {
                    num++;
                }
            }
        }
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    for _, row := range grid {
        for _, value := range row {
            if value < 0 {
                num++
            }
        }
    }
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        for row in grid:
            for value in row:
                if value < 0:
                    num += 1
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            if (grid[i][j] < 0) {
                num++;
            }
        }
    }
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    for (const row of grid) {
        for (const value of row) {
            if (value < 0) {
                num++;
            }
        }
    }
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    for (const row of grid) {
        for (const value of row) {
            if (value < 0) {
                num++;
            }
        }
    }
    return num;
};

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        for row in grid {
            for value in row {
                if value < 0 {
                    num += 1;
                }
            }
        }
        num
    }
}

复杂度分析

• 时间复杂度：$O(nm)$，即矩阵元素的总个数。
• 空间复杂度：$O(1)$。

方法二：二分查找

注意到题目中给了一个性质，即矩阵中的元素无论是按行还是按列，都以非递增顺序排列，可以考虑把这个性质利用起来优化暴力。已知这个性质告诉了我们每一行的数都是有序的，所以我们通过二分查找可以找到每一行中从前往后的第一个负数，那么这个位置之后到这一行的末尾里所有的数必然是负数了，可以直接统计。

1. 遍历矩阵的每一行。

2. 二分查找到该行从前往后的第一个负数，考虑第 $i$ 行，我们记这个位置为 $pos_i$，那么第 $i$ 行 $[pos_i,m-1]$ 中的所有数都是负数，所以这一行对答案的贡献就是 $m-1-pos_i+1=m-pos_i$。

3. 最后的答案就是 $\sum_{i=0}^{n-1}(m-pos_i)$。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        for (auto x : grid) {
            int l = 0, r = (int)x.size() - 1, pos = -1;
            while (l <= r) {
                int mid = l + ((r - l) >> 1);
                if (x[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            
            if (~pos) {  // pos != -1 表示这一行存在负数
                num += (int)x.size() - pos;
            }
        }
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        for (int[] row : grid) {
            int l = 0, r = row.length - 1, pos = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (row[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (pos != -1) {
                num += row.length - pos;
            }
        }
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        foreach (int[] row in grid) {
            int l = 0, r = row.Length - 1, pos = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (row[mid] < 0) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (pos != -1) {
                num += row.Length - pos;
            }
        }
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    for _, row := range grid {
        l, r, pos := 0, len(row) - 1, -1
        for l <= r {
            mid := l + (r - l) / 2
            if row[mid] < 0 {
                pos = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        if pos != -1 {
            num += len(row) - pos
        }
    }
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        for row in grid:
            l, r, pos = 0, len(row) - 1, -1
            while l <= r:
                mid = l + (r - l) // 2
                if row[mid] < 0:
                    pos = mid
                    r = mid - 1
                else:
                    l = mid + 1
            if pos != -1:
                num += len(row) - pos
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    for (int i = 0; i < gridSize; i++) {
        int l = 0, r = gridColSize[i] - 1, pos = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (grid[i][mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos != -1) {
            num += gridColSize[i] - pos;
        }
    }
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    for (const row of grid) {
        let l = 0, r = row.length - 1, pos = -1;
        while (l <= r) {
            const mid = l + Math.floor((r - l) / 2);
            if (row[mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos !== -1) {
            num += row.length - pos;
        }
    }
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    for (const row of grid) {
        let l = 0, r = row.length - 1, pos = -1;
        while (l <= r) {
            const mid = l + Math.floor((r - l) / 2);
            if (row[mid] < 0) {
                pos = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (pos !== -1) {
            num += row.length - pos;
        }
    }
    return num;
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        for row in grid {
            let (mut l, mut r, mut pos) = (0, row.len() as i32 - 1, -1);
            while l <= r {
                let mid = l + (r - l) / 2;
                if row[mid as usize] < 0 {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if pos != -1 {
                num += row.len() as i32 - pos;
            }
        }
        num
    }
}

复杂度分析

• 时间复杂度：二分查找一行的时间复杂度为$logm$，需要遍历$n$行，所以总时间复杂度是$O(nlogm)$。
• 空间复杂度：$O(1)$。

方法三：分治

方法二其实只利用了一部分的性质，即每一行是非递增的，但其实整个矩阵是每行每列均非递增，这说明了一个更重要的性质：每一行从前往后第一个负数的位置是不断递减的，即我们设第 $i$ 行的第一个负数的位置为 $pos_i$，不失一般性，我们把一行全是正数的 $pos$ 设为 $m$，则
$$
pos_0>=pos_1>=pos_2>=...>=pos_{n-1}
$$
所以我们可以依此设计一个分治算法。

我们设计一个函数 $solve(l,r,L,R)$ 表示我们在统计 $[l,r]$ 行的答案，第 $[l,r]$ 行 $pos$ 的位置在 $[L,R]$ 列中，计算 $[l,r]$ 的中间行第 $mid$ 行的的 $pos_{mid}$，算完以后根据之前的方法计算这一行对答案的贡献。然后根据我们之前发现的性质，可以知道 $[l,mid-1]$ 中所有行的 $pos$ 是大于等于 $pos_{mid}$，$[mid+1,r]$ 中所有行的 $pos$ 值是小于等于 $pos_{mid}$ 的，所以可以分成两部分递归下去，即：
$$
solve(l,mid-1,pos_{mid},R)
$$
和
$$
solve(mid+1,r,L,pos_{mid})
$$
所以答案就是 $m-pos_{mid}+solve(l,mid-1,pos_{mid},R)+solve(mid+1,r,L,pos_{mid})$。

递归函数入口为 $solve(0,n-1,0,m-1)$。

###C++

class Solution {
public:
    int solve(int l, int r, int L, int R, vector<vector<int>>& grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + ((r - l) >> 1);
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; ++i) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += (int)grid[0].size() - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R, grid);
        }
        
        return ans;
    }
    
    int countNegatives(vector<vector<int>>& grid) {
        return solve(0, (int)grid.size() - 1, 0, (int)grid[0].size() - 1, grid);
    }
};  

###Java

class Solution {
    private int solve(int l, int r, int L, int R, int[][] grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + (r - l) / 2;
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R, grid);
        }
        return ans;
    }
    
    public int countNegatives(int[][] grid) {
        return solve(0, grid.length - 1, 0, grid[0].length - 1, grid);
    }
}

###C#

public class Solution {
    private int Solve(int l, int r, int L, int R, int[][] grid) {
        if (l > r) {
            return 0;
        }
        
        int mid = l + (r - l) / 2;
        int pos = -1;
        // 在当前行中查找第一个负数
        for (int i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        int ans = 0;
        if (pos != -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].Length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += Solve(l, mid - 1, pos, R, grid);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += Solve(mid + 1, r, L, pos, grid);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += Solve(mid + 1, r, L, R, grid);
        }
        
        return ans;
    }
    
    public int CountNegatives(int[][] grid) {
        return Solve(0, grid.Length - 1, 0, grid[0].Length - 1, grid);
    }
}

###Go

func countNegatives(grid [][]int) int {
    var solve func(l, r, L, R int) int
    solve = func(l, r, L, R int) int {
        if l > r {
            return 0
        }
        
        mid := l + (r - l) / 2
        pos := -1
        // 在当前行中查找第一个负数
        for i := L; i <= R; i++ {
            if grid[mid][i] < 0 {
                pos = i
                break
            }
        }
        
        ans := 0
        if pos != -1 {
            // 当前行找到负数，计算当前行的负数个数
            ans += len(grid[0]) - pos
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid-1, pos, R)
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid+1, r, L, pos)
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid+1, r, L, R)
        }
        
        return ans
    }
    
    return solve(0, len(grid)-1, 0, len(grid[0])-1)
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        def solve(l: int, r: int, L: int, R: int) -> int:
            if l > r:
                return 0
            mid = l + (r - l) // 2
            pos = -1
            # 在当前行中查找第一个负数
            for i in range(L, R + 1):
                if grid[mid][i] < 0:
                    pos = i
                    break
            ans = 0
            if pos != -1:
                # 当前行找到负数，计算当前行的负数个数
                ans += len(grid[0]) - pos
                # 递归处理上半部分（使用更小的列范围）
                ans += solve(l, mid - 1, pos, R)
                # 递归处理下半部分（使用相同的列起始范围）
                ans += solve(mid + 1, r, L, pos)
            else:
                # 当前行没有负数，只需要递归处理下半部分
                ans += solve(mid + 1, r, L, R)

            return ans
            
        return solve(0, len(grid) - 1, 0, len(grid[0]) - 1)

###C

int solve(int l, int r, int L, int R, int** grid, int gridSize, int gridColSize) {
    if (l > r) {
        return 0;
    }
    
    int mid = l + (r - l) / 2;
    int pos = -1;
    // 在当前行中查找第一个负数
    for (int i = L; i <= R; i++) {
        if (grid[mid][i] < 0) {
            pos = i;
            break;
        }
    }
    
    int ans = 0;
    if (pos != -1) {
        // 当前行找到负数，计算当前行的负数个数
        ans += gridColSize - pos;
        // 递归处理上半部分（使用更小的列范围）
        ans += solve(l, mid - 1, pos, R, grid, gridSize, gridColSize);
        // 递归处理下半部分（使用相同的列起始范围）
        ans += solve(mid + 1, r, L, pos, grid, gridSize, gridColSize);
    } else {
        // 当前行没有负数，只需要递归处理下半部分
        ans += solve(mid + 1, r, L, R, grid, gridSize, gridColSize);
    }
    
    return ans;
}

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    return solve(0, gridSize - 1, 0, gridColSize[0] - 1, grid, gridSize, gridColSize[0]);
}

###JavaScript

var countNegatives = function(grid) {
    const solve = (l, r, L, R) => {
        if (l > r) {
            return 0;
        }
        
        const mid = l + Math.floor((r - l) / 2);
        let pos = -1;
        // 在当前行中查找第一个负数
        for (let i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        let ans = 0;
        if (pos !== -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R);
        }
        
        return ans;
    };
    
    return solve(0, grid.length - 1, 0, grid[0].length - 1);
};

###TypeScript

function countNegatives(grid: number[][]): number {
    const solve = (l: number, r: number, L: number, R: number): number => {
        if (l > r) {
            return 0;
        }
        
        const mid = l + Math.floor((r - l) / 2);
        let pos = -1;
        // 在当前行中查找第一个负数
        for (let i = L; i <= R; i++) {
            if (grid[mid][i] < 0) {
                pos = i;
                break;
            }
        }
        
        let ans = 0;
        if (pos !== -1) {
            // 当前行找到负数，计算当前行的负数个数
            ans += grid[0].length - pos;
            // 递归处理上半部分（使用更小的列范围）
            ans += solve(l, mid - 1, pos, R);
            // 递归处理下半部分（使用相同的列起始范围）
            ans += solve(mid + 1, r, L, pos);
        } else {
            // 当前行没有负数，只需要递归处理下半部分
            ans += solve(mid + 1, r, L, R);
        }
        
        return ans;
    };
    
    return solve(0, grid.length - 1, 0, grid[0].length - 1);
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        fn solve(l: i32, r: i32, L: i32, R: i32, grid: &Vec<Vec<i32>>) -> i32 {
            if l > r {
                return 0;
            }
            
            let mid = l + (r - l) / 2;
            let mut pos = -1;
            // 在当前行中查找第一个负数
            for i in L..=R {
                if grid[mid as usize][i as usize] < 0 {
                    pos = i;
                    break;
                }
            }
            
            let mut ans = 0;
            if pos != -1 {
                // 当前行找到负数，计算当前行的负数个数
                ans += grid[0].len() as i32 - pos;
                // 递归处理上半部分（使用更小的列范围）
                ans += solve(l, mid - 1, pos, R, grid);
                // 递归处理下半部分（使用相同的列起始范围）
                ans += solve(mid + 1, r, L, pos, grid);
            } else {
                // 当前行没有负数，只需要递归处理下半部分
                ans += solve(mid + 1, r, L, R, grid);
            }
            
            ans
        }
        
        solve(0, grid.len() as i32 - 1, 0, grid[0].len() as i32 - 1, &grid)
    }
}

复杂度分析

• 时间复杂度：代码中找第一个负数的位置是直接遍历 $[L,R]$ 找的，再考虑到 $n$ 和 $m$ 同阶，所以每个 $solve$ 函数里需要消耗 $O(n)$ 的时间，由主定理可得时间复杂度为：
  $$
  T(n)=2T(n/2)+O(n)=O(nlogn)
  $$

• 空间复杂度：$O(1)$。

方法四：倒序遍历

考虑方法三发现的性质，我们可以设计一个更简单的方法。考虑我们已经算出第 $i$ 行的从前往后第一个负数的位置 $pos_i$，那么第 $i+1$ 行的时候，$pos_{i+1}$ 的位置肯定是位于 $[0,pos_i]$ 中，所以对于第 $i+1$ 行我们倒着从 $pos_i$ 循环找 $pos_{i+1}$ 即可，这个循环起始变量是一直在递减的。

###C++

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int num = 0;
        int m = (int)grid[0].size();
        int pos = (int)grid[0].size() - 1;
        
        for (auto& row : grid) {
            int i;
            for (i = pos; i >= 0; --i) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
};

###Java

class Solution {
    public int countNegatives(int[][] grid) {
        int num = 0;
        int m = grid[0].length;
        int pos = grid[0].length - 1;
        
        for (int[] row : grid) {
            int i;
            for (i = pos; i >= 0; i--) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
}

###C#

public class Solution {
    public int CountNegatives(int[][] grid) {
        int num = 0;
        int m = grid[0].Length;
        int pos = grid[0].Length - 1;
        
        foreach (int[] row in grid) {
            int i;
            for (i = pos; i >= 0; i--) {
                if (row[i] >= 0) {
                    if (i + 1 < m) {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1) {
                num += m;
                pos = -1;
            }
        }
        
        return num;
    }
}

###Go

func countNegatives(grid [][]int) int {
    num := 0
    m := len(grid[0])
    pos := len(grid[0]) - 1
    
    for _, row := range grid {
        i := pos
        for ; i >= 0; i-- {
            if row[i] >= 0 {
                if i + 1 < m {
                    pos = i + 1
                    num += m - pos
                }
                break
            }
        }
        if i == -1 {
            num += m
            pos = -1
        }
    }
    
    return num
}

###Python

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        num = 0
        m = len(grid[0])
        pos = len(grid[0]) - 1
        
        for row in grid:
            i = pos
            while i >= 0:
                if row[i] >= 0:
                    if i + 1 < m:
                        pos = i + 1
                        num += m - pos
                    break
                i -= 1
            if i == -1:
                num += m
                pos = -1
        
        return num

###C

int countNegatives(int** grid, int gridSize, int* gridColSize) {
    int num = 0;
    int m = gridColSize[0];
    int pos = gridColSize[0] - 1;
    
    for (int i = 0; i < gridSize; i++) {
        int j;
        for (j = pos; j >= 0; j--) {
            if (grid[i][j] >= 0) {
                if (j + 1 < m) {
                    pos = j + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (j == -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
}

###JavaScript

var countNegatives = function(grid) {
    let num = 0;
    const m = grid[0].length;
    let pos = grid[0].length - 1;
    
    for (const row of grid) {
        let i;
        for (i = pos; i >= 0; i--) {
            if (row[i] >= 0) {
                if (i + 1 < m) {
                    pos = i + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (i === -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
};

###TypeScript

function countNegatives(grid: number[][]): number {
    let num = 0;
    const m = grid[0].length;
    let pos = grid[0].length - 1;
    
    for (const row of grid) {
        let i: number;
        for (i = pos; i >= 0; i--) {
            if (row[i] >= 0) {
                if (i + 1 < m) {
                    pos = i + 1;
                    num += m - pos;
                }
                break;
            }
        }
        if (i === -1) {
            num += m;
            pos = -1;
        }
    }
    
    return num;
}

###Rust

impl Solution {
    pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
        let mut num = 0;
        let m = grid[0].len();
        let mut pos = (grid[0].len() - 1) as i32;
        
        for row in grid {
            let mut i = pos;
            while i >= 0 {
                if row[i as usize] >= 0 {
                    if i + 1 < m as i32 {
                        pos = i + 1;
                        num += (m as i32) - pos;
                    }
                    break;
                }
                i -= 1;
            }
            if i == -1 {
                num += m as i32;
                pos = -1;
            }
        }
        
        num
    }
}

复杂度分析

• 时间复杂度：考虑每次循环变量的起始位置是单调不降的，所以起始位置最多移动 $m$ 次，时间复杂度 $O(n+m)$。
• 空间复杂度：$O(1)$。

方法一：时间戳排序

思路与算法

我们可以将所有活动的左右边界放在一起进行自定义排序。具体地，我们用 $(\textit{ts}, \textit{op}, \textit{val})$ 表示一个「事件」：

• $\textit{op}$ 表示该事件的类型。如果 $\textit{op} = 0$，说明该事件表示一个活动的开始；如果 $\textit{op} = 1$，说明该事件表示一个活动的结束。

• $\textit{ts}$ 表示该事件发生的时间，即活动的开始时间或结束时间。

• $\textit{val}$ 表示该事件的价值，即对应活动的 $\textit{value}$ 值。

我们将所有的时间按照 $\textit{ts}$ 为第一关键字升序排序，这样我们就能按照时间顺序依次处理每一个事件。当 $\textit{ts}$ 相等时，我们按照 $\textit{op}$ 为第二关键字升序排序，这是因为题目中要求了「第一个活动的结束时间不能等于第二个活动的起始时间」，因此当时间相同时，我们先处理开始的事件，再处理结束的事件。

当排序完成后，我们就可以通过对所有的事件进行一次遍历，从而算出最多两个时间不重叠的活动的最大价值：

• 当我们遍历到一个结束事件时，我们用 $\textit{val}$ 来更新 $\textit{bestFirst}$，其中 $\textit{bestFirst}$ 表示当前已经结束的所有活动的最大价值。这样做的意义在于，所有已经结束的事件都可以当作第一个活动。

• 当我们遍历到一个开始事件时，我们将该活动当作第二个活动，由于第一个活动的最大价值为 $\textit{bestFirst}$，因此我们用 $\textit{val} + \textit{bestFirst}$ 更新答案即可。

代码

###C++

struct Event {
    // 时间戳
    int ts;
    // op = 0 表示左边界，op = 1 表示右边界
    int op;
    int val;
    Event(int _ts, int _op, int _val): ts(_ts), op(_op), val(_val) {}
    bool operator< (const Event& that) const {
        return tie(ts, op) < tie(that.ts, that.op);
    }
};

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        vector<Event> evs;
        for (const auto& event: events) {
            evs.emplace_back(event[0], 0, event[2]);
            evs.emplace_back(event[1], 1, event[2]);
        }
        sort(evs.begin(), evs.end());
        
        int ans = 0, bestFirst = 0;
        for (const auto& [ts, op, val]: evs) {
            if (op == 0) {
                ans = max(ans, val + bestFirst);
            }
            else {
                bestFirst = max(bestFirst, val);
            }
        }
        return ans;
    }
};

###Python

class Event:
    def __init__(self, ts: int, op: int, val: int):
        self.ts = ts
        self.op = op
        self.val = val
    
    def __lt__(self, other: "Event") -> bool:
        return (self.ts, self.op) < (other.ts, other.op)


class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        evs = list()
        for event in events:
            evs.append(Event(event[0], 0, event[2]))
            evs.append(Event(event[1], 1, event[2]))
        evs.sort()

        ans = bestFirst = 0
        for ev in evs:
            if ev.op == 0:
                ans = max(ans, ev.val + bestFirst)
            else:
                bestFirst = max(bestFirst, ev.val)
        
        return ans

###Java

class Solution {
    public int maxTwoEvents(int[][] events) {
        List<Event> evs = new ArrayList<>();
        for (int[] event : events) {
            evs.add(new Event(event[0], 0, event[2]));
            evs.add(new Event(event[1], 1, event[2]));
        }
        Collections.sort(evs);
        int ans = 0, bestFirst = 0;
        for (Event event : evs) {
            if (event.op == 0) {
                ans = Math.max(ans, event.val + bestFirst);
            } else {
                bestFirst = Math.max(bestFirst, event.val);
            }
        }
        return ans;
    }
    
    class Event implements Comparable<Event> {
        int ts;
        int op;
        int val;
        
        Event(int ts, int op, int val) {
            this.ts = ts;
            this.op = op;
            this.val = val;
        }
        
        @Override
        public int compareTo(Event other) {
            if (this.ts != other.ts) {
                return Integer.compare(this.ts, other.ts);
            }
            return Integer.compare(this.op, other.op);
        }
    }
}

###C#

public class Solution {
    public int MaxTwoEvents(int[][] events) {
        List<Event> evs = new List<Event>();
        foreach (var eventArr in events) {
            evs.Add(new Event(eventArr[0], 0, eventArr[2]));
            evs.Add(new Event(eventArr[1], 1, eventArr[2]));
        }
        evs.Sort();
        
        int ans = 0, bestFirst = 0;
        foreach (var ev in evs) {
            if (ev.Op == 0) {
                ans = Math.Max(ans, ev.Val + bestFirst);
            } else {
                bestFirst = Math.Max(bestFirst, ev.Val);
            }
        }
        return ans;
    }
    
    class Event : IComparable<Event> {
        public int Ts { get; set; }
        public int Op { get; set; }
        public int Val { get; set; }
        
        public Event(int ts, int op, int val) {
            Ts = ts;
            Op = op;
            Val = val;
        }
        
        public int CompareTo(Event other) {
            if (Ts != other.Ts) {
                return Ts.CompareTo(other.Ts);
            }
            return Op.CompareTo(other.Op);
        }
    }
}

###Go

func maxTwoEvents(events [][]int) int {
    type Event struct {
        ts  int
        op  int
        val int
    }
    
    evs := make([]Event, 0)
    for _, event := range events {
        evs = append(evs, Event{event[0], 0, event[2]})
        evs = append(evs, Event{event[1], 1, event[2]})
    }
    
    sort.Slice(evs, func(i, j int) bool {
        if evs[i].ts != evs[j].ts {
            return evs[i].ts < evs[j].ts
        }
        return evs[i].op < evs[j].op
    })
    
    ans, bestFirst := 0, 0
    for _, ev := range evs {
        if ev.op == 0 {
            if ev.val + bestFirst > ans {
                ans = ev.val + bestFirst
            }
        } else {
            if ev.val > bestFirst {
                bestFirst = ev.val
            }
        }
    }
    return ans
}

###C

typedef struct {
    int ts;
    int op;
    int val;
} Event;

int compareEvents(const void* a, const void* b) {
    Event* e1 = (Event*)a;
    Event* e2 = (Event*)b;
    if (e1->ts != e2->ts) {
        return e1->ts - e2->ts;
    }
    return e1->op - e2->op;
}

int maxTwoEvents(int** events, int eventsSize, int* eventsColSize) {
    Event* evs = (Event*)malloc(2 * eventsSize * sizeof(Event));
    int idx = 0;
    for (int i = 0; i < eventsSize; i++) {
        evs[idx++] = (Event){events[i][0], 0, events[i][2]};
        evs[idx++] = (Event){events[i][1], 1, events[i][2]};
    }
    qsort(evs, 2 * eventsSize, sizeof(Event), compareEvents);

    int ans = 0, bestFirst = 0;
    for (int i = 0; i < 2 * eventsSize; i++) {
        if (evs[i].op == 0) {
            if (evs[i].val + bestFirst > ans) {
                ans = evs[i].val + bestFirst;
            }
        } else {
            if (evs[i].val > bestFirst) {
                bestFirst = evs[i].val;
            }
        }
    }
    
    free(evs);
    return ans;
}

###JavaScript

var maxTwoEvents = function(events) {
    const evs = [];
    for (const event of events) {
        evs.push({ts: event[0], op: 0, val: event[2]});
        evs.push({ts: event[1], op: 1, val: event[2]});
    }
    
    evs.sort((a, b) => {
        if (a.ts !== b.ts) {
            return a.ts - b.ts;
        }
        return a.op - b.op;
    });
    
    let ans = 0, bestFirst = 0;
    for (const ev of evs) {
        if (ev.op === 0) {
            ans = Math.max(ans, ev.val + bestFirst);
        } else {
            bestFirst = Math.max(bestFirst, ev.val);
        }
    }
    return ans;
};

###TypeScript

function maxTwoEvents(events: number[][]): number {
    interface Event {
        ts: number;
        op: number;
        val: number;
    }
    
    const evs: Event[] = [];
    for (const event of events) {
        evs.push({ts: event[0], op: 0, val: event[2]});
        evs.push({ts: event[1], op: 1, val: event[2]});
    }
    
    evs.sort((a, b) => {
        if (a.ts !== b.ts) {
            return a.ts - b.ts;
        }
        return a.op - b.op;
    });
    
    let ans = 0, bestFirst = 0;
    for (const ev of evs) {
        if (ev.op === 0) {
            ans = Math.max(ans, ev.val + bestFirst);
        } else {
            bestFirst = Math.max(bestFirst, ev.val);
        }
    }
    return ans;
}

###Rust

#[derive(Debug)]
struct Event {
    ts: i32,
    op: i32,
    val: i32,
}

impl Solution {
    pub fn max_two_events(events: Vec<Vec<i32>>) -> i32 {
        let mut evs: Vec<Event> = Vec::new();
        for event in events {
            evs.push(Event { ts: event[0], op: 0, val: event[2] });
            evs.push(Event { ts: event[1], op: 1, val: event[2] });
        }
        
        evs.sort_by(|a, b| {
            if a.ts != b.ts {
                a.ts.cmp(&b.ts)
            } else {
                a.op.cmp(&b.op)
            }
        });
        
        let mut ans = 0;
        let mut best_first = 0;
        for ev in evs {
            if ev.op == 0 {
                ans = ans.max(ev.val + best_first);
            } else {
                best_first = best_first.max(ev.val);
            }
        }
        
        ans
    }
}

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{events}$ 的长度。

• 空间复杂度：$O(n)$。