You are viewing a single comment's thread. Return to all comments →
C# solution:
public static long gridlandMetro(int n, int m, int k, List<List<int>> track) { var rowTracks = new Dictionary<int, List<List<int>>> { }; var numTracks = track.Count; if (numTracks == 0) return ((long)n) * m; for(var i = 0; i < numTracks; i++) { var nextTrack = track[i]; var row = nextTrack[0]; if (!rowTracks.TryGetValue(nextTrack[0], out _)) { rowTracks[row] = new List<List<int>> { }; } nextTrack.RemoveAt(0); rowTracks[row].Add(nextTrack); } var rowsWithTracks = rowTracks.Keys.ToList(); rowsWithTracks.Sort(); var numRowsWithTracks = rowsWithTracks.Count; var emptyRows = n - numRowsWithTracks; long numFree = (long)emptyRows * m; foreach(var row in rowsWithTracks) { var segs = rowTracks[row]; var distinctSegs = MakeDistinctIntervals(segs); var prevRight = 0; var maxLeft = m; foreach(var seg in distinctSegs) { numFree += seg[0] - prevRight -1L; prevRight = seg[1]; } numFree += (long)m - prevRight; } return numFree; } public static List<List<int>> MakeDistinctIntervals(List<List<int>> segs) { var numSegs = segs.Count; if (numSegs == 1) return segs; var result = new List<List<int>> { }; var minLeft = segs.Select(seg => seg[0]).Min(); var minLeftRight = segs.Where(seg => seg[0] == minLeft).Select(seg => seg[1]).Max(); var allIntersecting = segs.Where(seg => minLeft <= seg[0] && seg[0] <= minLeftRight +1); var minLeftMaxRight = allIntersecting.Select(segs => segs[1]).Max(); var leftmostSeg = new List<int> { minLeft, minLeftMaxRight }; result.Add(leftmostSeg); var remaining = segs.Where(seg => seg[0] > minLeftMaxRight).ToList(); if (remaining.Count > 0) { var allRightSegs = MakeDistinctIntervals(remaining); result.AddRange(allRightSegs); } return result; }
Seems like cookies are disabled on this browser, please enable them to open this website
Gridland Metro
You are viewing a single comment's thread. Return to all comments →
C# solution: