package LeetCode_539

import java.util.*

/**
 * 539. Minimum Time Difference
 * https://leetcode.com/problems/minimum-time-difference/
 * Given a list of 24-hour clock time points in "HH:MM" format, return the minimum minutes difference between any two time-points in the list.

Example 1:
Input: timePoints = ["23:59","00:00"]
Output: 1

Example 2:
Input: timePoints = ["00:00","23:59","00:00"]
Output: 0

Constraints:
1. 2 <= timePoints <= 2 * 10^4
2. timePoints[i] is in the format "HH:MM".
 * */
class Solution {
    /*
    * solution: PriorityQueue, change time into num then insert into minHeap and calculate the min diff of any two elements.
    * Time:O(nlogn), Space:O(n)
    * */
    fun findMinDifference(timePoints: List<String>): Int {
        val minHeap = PriorityQueue<Int>()
        for (time in timePoints) {
            val times = time.split(":")
            val h = times[0].toInt()
            val m = times[1].toInt()
            //insert minutes
            minHeap.add(h * 60 + m)
        }
        var result = Int.MAX_VALUE
        val first = minHeap.poll()
        var cur = first
        while (minHeap.isNotEmpty()) {
            val next = minHeap.poll()
            //compare between any two times
            result = Math.min(result, next - cur)
            cur = next
        }
        /*
        * because need compare between any two times, also need compare the first and last, because the different is 24 hours,
          so the first time need add 24*60
        * */
        result = Math.min(result, 24*60+first-cur)
        return result
    }
}