Flame Chan56. Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4
Original Page
public int[][] merge(int[][] intervals) {
if(intervals.length <= 1){
return intervals;
}
Arrays.sort(intervals, (a,b)->{
return Integer.compare(a[0], b[0]);
});
List<int[]> list = new ArrayList();
for(int i=1; i<intervals.length; i++){
if(intervals[i-1][1] >= intervals[i][0]){
intervals[i][0] = intervals[i-1][0];
intervals[i][1] = Math.max(intervals[i-1][1], intervals[i][1]);
} else{
list.add(intervals[i-1]);
}
}
list.add(intervals[intervals.length-1]);
return list.toArray(new int[list.size()][]);
}
738. Monotone Increasing Digits
An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.
Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.
Example 1:
Input: n = 10
Output: 9
Example 2:
Input: n = 1234
Output: 1234
Example 3:
Input: n = 332
Output: 299
Constraints:
0 <= n <= 10^9
public int monotoneIncreasingDigits(int n) {
if(n<10){
return n;
}
String str = Integer.toString(n);
char[] arr = new char[str.length()];
arr[0] = str.charAt(0);
int pos = -1;
for(int i=1; i<str.length(); i++){
char num = str.charAt(i);
if(num < arr[i-1]){
int j;
if(pos == -1){
j = 0;
}else{
j = pos;
}
for(;j<arr.length; j++){
if(j==0||j==pos){
arr[j] = (char) (arr[j]-1);
}else{
arr[j] = '9';
}
}
break;
}
else if(num > arr[i-1]){
pos = i;
}
arr[i] = str.charAt(i);
}
if(arr[0] <=0){
// cost space by using String
str = new String(arr, 1,arr.length);
}else{
str = new String(arr);
}
return Integer.valueOf(str);
}
