Java Code, similar to Merge Intervals, beat 99%


  • 0
    C
    class Range {
        int start;
        int end;
        public Range(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public class Solution {
        public int[] smallestRange(List<List<Integer>> nums) {
            if (nums.size() == 1) {
                int a = nums.get(0).get(0);
                int[] res = new int[]{a, a};
                return res;
            }
            List<Range> list = new ArrayList<>();
            for (int a : nums.get(0)) {
                list.add(new Range(a, a));
            }
            for (int i = 1; i < nums.size(); i++) {
                list = merge(list, nums.get(i));
            }
            return getShortestRange(list);
        }
        private List<Range> merge(List<Range> list, List<Integer> num) {
            List<Range> res = new ArrayList<>();
            int i = 0; 
            int j = 0; 
            while (j < num.size() && i < list.size()) {
                if (num.get(j) <= list.get(i).end) {
                    if (j != num.size() - 1 && num.get(j + 1) <= list.get(i).end) {
                        j++;
                    } else if (num.get(j) < list.get(i).start) {
                        res.add(new Range(num.get(j), list.get(i).end));
                        j++;
                    } else {
                        res.add(new Range(list.get(i).start, list.get(i).end));
                        i++;
                    }
                } else if (i != list.size() - 1 && num.get(j) >= list.get(i + 1).end) {
                    i++;
                } else {
                    res.add(new Range(list.get(i).start, num.get(j)));
                    i++;
                }
            }
            return res;
        }
        private int[] getShortestRange(List<Range> list) {
            Range res = list.get(0);
            int diff = res.end - res.start;
            for (Range r : list) {
                if (r.end - r.start < diff) {
                    diff = r.end - r.start;
                    res = r;
                }
            }
            return new int[]{res.start, res.end};
        }
    }
    

  • 0
    Q

    Can you give some comments of your code?
    Why is it correct?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.