Minimum Time Difference - DP(ish) solution
Problem is here: https://leetcode.com/problems/minimum-time-difference/description/
Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.
Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.
Example 1:
Input: ["23:59","00:00"] Output: 1
Note:
- The number of time points in the given list is at least 2 and won't exceed 20000.
- The input time is legal and ranges from 00:00 to 23:59.
- Basically the input range is very small: it fits into a 1500 array
- Create a bool array of this size and map each time to it
- If the time has already been set, return 0 (that's the min)
- This cost linear time and constant space (O(1500))
- Next traverse the array and compare the two adjacent cells that have a time on it
- Some extra check is needed for the boundary case when the min diff crosses the day line
That's it! Cheers, Marcelo
public class Solution
{
public int FindMinDifference(IList timePoints)
{
if (timePoints == null) return 0;
bool[] map = new bool[1500];
int min = Int32.MaxValue;
int max = Int32.MinValue;
foreach (string t in timePoints)
{
string[] parts = t.Split(':');
int val = Int32.Parse(parts[0]) * 60 + Int32.Parse(parts[1]);
if (map[val]) return 0;
map[val] = true;
min = Math.Min(min, val);
max = Math.Max(max, val);
}
int solution = Math.Abs(24 * 60 - (max - min));
int previousIndex = min;
for (int i = min + 1; i < map.Length; i++)
{
if (map[i])
{
solution = Math.Min(solution, i - previousIndex);
previousIndex = i;
}
}
return solution;
}
}
Comments
Nicely done! Since the input size is so small, I've decided to use a sort-based approach:
Reply Delete1) convert all times to minutes
2) sort all the times
3) find the minimum difference between 2 successive times and compare it with the corner case where the time between the largest and smallest times is the smallest. The code in Rust is below:
impl Solution {
pub fn find_min_difference(time_points: Vec) -> i32 {
fn to_minutes(time: &str) -> i32 {
let parts: Vec<_> = time.split(":").collect();
let hours: i32 = parts[0].parse().unwrap();
let minutes: i32 = parts[1].parse().unwrap();
hours * 60 + minutes
}
let mut minutes: Vec<_> = time_points.iter().map(|t| to_minutes(&t)).collect();
minutes.sort_unstable();
std::cmp::min(
minutes.iter().zip(minutes.iter().skip(1)).map(|(x, y)| y - x).min().unwrap(),
minutes[0] + 1440 - minutes.last().unwrap(),
)
}
}
https://gist.github.com/ttsugriy/81bd95b2781a57065580789fba4f80a2
Cheers,
Taras
Post a Comment
[γγ¬γΌγ ]