LeetCode DayGreedy Algorithms Part 5

56. 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 list = new ArrayList();
        for(int i=1; i= 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 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);
    }








          

            
        
The above is the detailed content of LeetCode DayGreedy Algorithms Part 5. For more information, please follow other related articles on the PHP Chinese website!