Java sorting with a sentinel node


  • 8
    Z
    public class Solution {
        public int findMinDifference(List<String> timePoints) {
            int n = timePoints.size();
            List<Time> times = new ArrayList<>();
            for (String tp : timePoints) {
                String[] strs = tp.split(":");
                times.add(new Time(Integer.parseInt(strs[0]), Integer.parseInt(strs[1])));
            }
            Collections.sort(times);
            Time earlist = times.get(0);
            times.add(new Time(earlist.h + 24, earlist.m));
            int minDiff = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                int diff = (int) Math.abs(times.get(i).getDiff(times.get(i + 1)));
                minDiff = Math.min(minDiff, diff);
            }
            return minDiff;
        }
        
    }
    
    class Time implements Comparable<Time> {
        int h;
        int m;
        public Time(int h, int m) {
            this.h = h;
            this.m = m;
        }
        
        public int compareTo(Time other) {
            if (this.h == other.h) {
                return this.m - other.m;
            }
            return this.h - other.h;
        }
        
        public int getDiff(Time other) {
            return (this.h - other.h) * 60 + (this.m - other.m);            
        }
    }
    

  • 1
    G

    @zzwcsong, thanks for the efficient solution. I've got a query - could you please clarify the usage of:

    Time earlist = times.get(0);
            times.add(new Time(earlist.h + 24, earlist.m)); 
    

    I know you're getting the first sorted Time object, but I didn't quite understand the part earlist.h + 24 . Thanks in advance.


  • 2
    Z

    @giwmcoder Hi, the idea is to duplicate the earliest moment in out input.

    Let's say, we have a input [2:00, 7:30, 14:30, 23:00], the minimal difference should be 3 hours for 2:00 and 23:00, but if we don't process the array, it will give us 21 hours instead of 3 hours.
    After this step, it would become [2:00, 7:30, 14:30, 20:00, 26:00]. (26:00 is another way to represent the earliest moment 2:00), now we can handle this case successfully.

    Hope it helps.


  • 0
    G

    Hi @zzwcsong , thank you so much for the clarification. It definitely makes sense now. Thanks! :)


  • 1
    Y

    Same idea, but I guess it is simpler...

    public class Solution {
        private int getSeconds(String timePoint) {
            String[] splittedTimePoint = timePoint.split(":");
            return Integer.parseInt(splittedTimePoint[0]) * 60 + Integer.parseInt(splittedTimePoint[1]);
        }
        public int findMinDifference(List<String> timePoints) {
            Collections.sort(timePoints);
            int minDiff = Integer.MAX_VALUE;
            for (int i = 1; i < timePoints.size(); ++i) {
                minDiff = Math.min(minDiff, getSeconds(timePoints.get(i)) - getSeconds(timePoints.get(i - 1)));
            }
            return Math.min(minDiff, getSeconds(timePoints.get(0)) + 1440 - getSeconds(timePoints.get(timePoints.size() - 1)));
        }
    }
    

  • 0
    Z

    @yl That's great, thanks for sharing


  • 0

    Same idea, but findign min during sort.

    public int findMinDifference(List<String> list) {
        if(list == null || list.size() == 0) return 0;
        int[] min = new int[] {Integer.MAX_VALUE};
        Collections.sort(list, (a, b) -> {min[0] = Math.min(diff(a, b, 0), min[0]); return a.compareTo(b);});
        return Math.min(min[0], diff(list.get(0), list.get(list.size() - 1), 24 * 60));
    }
    private int diff(String a, String b, int extraMins) {
        String[] aa = a.split(":"), bb = b.split(":");
        int minA = Integer.parseInt(aa[0]) * 60 + Integer.parseInt(aa[1]) + extraMins;
        int minB = Integer.parseInt(bb[0]) * 60 + Integer.parseInt(bb[1]);
        return Math.abs(minA - minB);
    }

Log in to reply
 

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