2345. Finding the Number of Visible Mountains
O(nlogn)
```java
class Solution {
public int visibleMountains(int[][] peaks) {
int n = peaks.length;
int[][] x = new int[peaks.length][2];
// see base of the moutain
for (int i = 0; i < peaks.length; i++) {
int px = peaks[i][0];
int py = peaks[i][1];
x[i][0] = px - py;
x[i][1] = px + py;
}
// when s are the same, we want this (for case2 using)
// 1 4
// 1 2
Arrays.sort(x, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int count = 0;
int i = 0;
while (i < n) {
int j = i+1;
// case1:
// if j is the last montain, count it
// if i and j montain, start or end are not the same, means we can see "one montain"
if (j == n || x[i][0] != x[j][0] || x[i][1] != x[j][1]) { // s != or e !=
count++;
}
// case2: if i_start i_end includes entire j, skip this j montain
while (j < n && x[i][0] <= x[j][0] && x[j][1] <= x[i][1]) { // including case, skip: j interval is including in i interval
j++;
}
i = j; // move to j
}
return count;
}
}
/*
[[2,2],[6,3],[5,4]]
0, 4
3,9
1, 9
[[2,2],[5,2],[8,4], [8,4], [8,4], [8,4],[8,4]]
0, 4
3 , 7
4, 12
0 4
1 9
3 9
is js je ie
*/
```
Last updated