Skip to content

3631. Sort Threats by Severity and Exploitability πŸ”’

Description

You are given a 2D integer array threats, where each threats[i] = [IDi, sevi​, expi]

  • IDi: Unique identifier of the threat.
  • sevi: Indicates the severity of the threat.
  • expi: Indicates the exploitability of the threat.

The score of a threat i is defined as: score = 2 × sevi + expi

Your task is to return threats sorted in descending order of score.

If multiple threats have the same score, sort them by ascending ID​​​​​​​.

 

Example 1:

Input: threats = [[101,2,3],[102,3,2],[103,3,3]]

Output: [[103,3,3],[102,3,2],[101,2,3]]

Explanation:

Threat ID sev exp Score = 2 × sev + exp
threats[0] 101 2 3 2 × 2 + 3 = 7
threats[1] 102 3 2 2 × 3 + 2 = 8
threats[2] 103 3 3 2 × 3 + 3 = 9

Sorted Order: [[103, 3, 3], [102, 3, 2], [101, 2, 3]]

Example 2:

Input: threats = [[101,4,1],[103,1,5],[102,1,5]]

Output: [[101,4,1],[102,1,5],[103,1,5]]

Explanation:​​​​​​​

Threat ID sev exp Score = 2 × sev + exp
threats[0] 101 4 1 2 × 4 + 1 = 9
threats[1] 103 1 5 2 × 1 + 5 = 7
threats[2] 102 1 5 2 × 1 + 5 = 7

threats[1] and threats[2] have same score, thus sort them by ascending ID.

Sorted Order: [[101, 4, 1], [102, 1, 5], [103, 1, 5]]

 

Constraints:

  • 1 <= threats.length <= 105
  • threats[i] == [IDi, sevi, expi]
  • 1 <= IDi <= 106
  • 1 <= sevi <= 109
  • 1 <= expi <= 109
  • All IDi are unique

Solutions

Solution 1: Sorting

We can directly sort the array according to the requirements of the problem. Note that the score is a long integer, so we need to use long integers when comparing to avoid overflow.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\text{threats}\).

1
2
3
4
class Solution:
    def sortThreats(self, threats: List[List[int]]) -> List[List[int]]:
        threats.sort(key=lambda x: (-(x[1] * 2 + x[2]), x[0]))
        return threats

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int[][] sortThreats(int[][] threats) {
        Arrays.sort(threats, (a, b) -> {
            long score1 = 2L * a[1] + a[2];
            long score2 = 2L * b[1] + b[2];
            if (score1 == score2) {
                return Integer.compare(a[0], b[0]);
            }
            return Long.compare(score2, score1);
        });
        return threats;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<vector<int>> sortThreats(vector<vector<int>>& threats) {
        sort(threats.begin(), threats.end(), [](const vector<int>& a, const vector<int>& b) {
            long long score1 = 2LL * a[1] + a[2];
            long long score2 = 2LL * b[1] + b[2];
            if (score1 == score2) {
                return a[0] < b[0];
            }
            return score2 < score1;
        });
        return threats;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func sortThreats(threats [][]int) [][]int {
    sort.Slice(threats, func(i, j int) bool {
        score1 := 2*int64(threats[i][1]) + int64(threats[i][2])
        score2 := 2*int64(threats[j][1]) + int64(threats[j][2])
        if score1 == score2 {
            return threats[i][0] < threats[j][0]
        }
        return score2 < score1
    })
    return threats
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function sortThreats(threats: number[][]): number[][] {
    threats.sort((a, b) => {
        const score1 = 2 * a[1] + a[2];
        const score2 = 2 * b[1] + b[2];
        if (score1 === score2) {
            return a[0] - b[0];
        }
        return score2 - score1;
    });
    return threats;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn sort_threats(mut threats: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        threats.sort_by(|a, b| {
            let score1 = 2i64 * a[1] as i64 + a[2] as i64;
            let score2 = 2i64 * b[1] as i64 + b[2] as i64;
            if score1 == score2 {
                a[0].cmp(&b[0])
            } else {
                score2.cmp(&score1)
            }
        });
        threats
    }
}

Comments