The city of Gridland is represented as an
n X m
matrix where the rows are numbered from1
ton
and the columns are numbered from1
tom
.Gridland has a network of train tracks that always run in straight horizontal lines along a row. In other words, the start and end points of a train track are (r, c1) and (r, c2), where
r
represents the row number, c1 represents the starting column, and c2 represents the ending column of the train track.The mayor of Gridland is surveying the city to determine the number of locations where lampposts can be placed. A lamppost can be placed in any cell that is not occupied by a train track.
Given a map of Gridland and its
k
train tracks, find and print the number of cells where the mayor can place lampposts.Note: A train track may (or may not) overlap other train tracks within the same row.
Input Format
The first line contains three space-separated integers describing the respective values of
n
(the number of rows),m
(the number of columns), andk
(the number of train tracks).Each line
i
of thek
subsequent lines contains three space-separated integers describing the respective values ofr
, c1, and c2 that define a train track.Constraints
• 1 ≤ n, m ≤ 109
• 0 ≤ k ≤ 1000
• 1 ≤ r ≤ n
• 1 ≤ c1 ≤ c2 ≤ m
Output Format
Print a single integer denoting the number of cells where the mayor can install lampposts.
Sample Input
4 4 3
2 2 3
3 1 4
4 4 4
Sample Output
9
Explanation
In the diagram above, the yellow cells denote the first train track, green denotes the second, and blue denotes the third. Lampposts can be placed in any of the nine red cells, so we print
9
as our answer.
My introduction of algorithm
The Gridland Metro is the medium level algorithm in the contest of Hackerrank World CodeSprint 7 in Sept. 2016. I did manage to solve the algorithm in the contest but I spend too many hours, problems are related to runtime error and timeout, the test cases I used in the code does not help to figure out the issue. Since n
,m
and k
are with large value and I did not have good techniques to work on simulation of large test cases, I examined the code and remembered the coding guideline phrase "express the intent", and then change a for loop to one statement to get distinct rows with train tracks first, in the function CalculateNumberOfCellsTakenByTrainTracks
, first statement:var distinctRowsOfTrainTracks = rowsOfTrainTracks.Distinct().ToArray()
.
Today I spent near 2 hours to review the C# algorithm, and put together the readable code, I have to relearn the algorithm and also write code with less smells, with some instructional notes.
The code passes all test cases on hackerrank.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace GridlandMetro
{
/*
* problem statement:
* https://www.hackerrank.com/contests/world-codesprint-7/challenges/gridland-metro
*/
public class MyComparer : IComparer<Tuple<int, int>>
{
public int Compare(Tuple<int, int> x, Tuple<int, int> y)
{
return (x.Item1 - y.Item1);
}
}
class Program
{
static void Main(string[] args)
{
//RunSampleTestcase();
//RunSampleTestcase2();
ProcessInput();
}
/*
* Sample test case in the problem statement.
* The result should be 9 since
* 7 cells are taken by 3 train tracks.
*/
private static void RunSampleTestcase()
{
int k = 3;
int rows = 4;
int columns = 4;
var map = new int[k];
var rowsOfTrainTracks = new List<int>();
var trainTrackColumns = new List<Tuple<int, int>>();
var trainTracks = new int[3, 3]{
{2,2,3},
{3,1,4},
{4,4,4}
};
for (int i = 0; i < k; i++)
{
int row = trainTracks[i, 0];
int startColumn = trainTracks[i, 1];
int endColumn = trainTracks[i, 2];
rowsOfTrainTracks.Add(row);
trainTrackColumns.Add(new Tuple<int, int>(startColumn, endColumn));
}
long cellNumberTakenByTrainTracks = CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTrackColumns);
long cellsForLampposts = rows * columns - cellNumberTakenByTrainTracks;
Debug.Assert(cellsForLampposts == 9);
}
/*
* Test case:
* Row No 2: 4 train tracks, 8 cells are taken by 4 train tracks.
* 1 - 4 reserved for train track - merge two of [1,4],[2,3]
* 6 - 7 train track
* 9 - 9 train track
*/
private static void RunSampleTestcase2()
{
int k = 5; // 5 train tracks
int rows = 2;
int columns = 10;
var map = new int[k];
var rowsOfTrainTracks = new List<int>();
var trainTrackColumns = new List<Tuple<int, int>>();
var trainTracks = new int[5, 3]{
{2,8,9},
{2,2,3},
{1,1,4},
{2,1,4},
{2,6,7}
};
for (int i = 0; i < k; i++)
{
int row = trainTracks[i, 0];
int startColumn = trainTracks[i, 1];
int endColumn = trainTracks[i, 2];
rowsOfTrainTracks.Add(row);
trainTrackColumns.Add(new Tuple<int, int>(startColumn, endColumn));
}
long cellNumberTakenByTrainTracks = CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTrackColumns);
long cellsForLampposts = rows * columns - cellNumberTakenByTrainTracks;
Debug.Assert(cellsForLampposts == 8);
}
public static void ProcessInput()
{
string[] summaryRow = Console.ReadLine().Split(' ');
int rowNumber = Convert.ToInt32(summaryRow[0]);
int columnNumber = Convert.ToInt32(summaryRow[1]);
int k = Convert.ToInt32(summaryRow[2]);
var map = new int[k];
var rowsOfTrainTracks = new List<int>();
var trainTracks = new List<Tuple<int, int>>();
for (int i = 0; i < k; i++)
{
var rowData = Console.ReadLine().Split(' ');
int rowNo = Convert.ToInt32(rowData[0]);
int startColumn = Convert.ToInt32(rowData[1]);
int endColumn = Convert.ToInt32(rowData[2]);
rowsOfTrainTracks.Add(rowNo);
trainTracks.Add(new Tuple<int, int>(startColumn, endColumn));
}
long sum = rowNumber;
sum *= columnNumber;
Console.WriteLine(sum - CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTracks));
}
/*
* requirement:
* 1. Lampposts can not be placed on a train track
* 2. Train track is always on horizontal row, and train tracks may overlap other train tracks
* within the same row
* 3. Calculate the number of cells where the mayor can place lampposts
*
* Design:
* merge intervals for each row - it is classical problem of Leetcode 56: Merge Intervals
*
* @rowsOfTrainTracks - row number for each train track
* @trainTracks - train track's start column and end column
*
* train tracks row information: rowsOfTrainTracks
* and each train track's columns information are stored in trainTracks respectively
*
*/
public static long CalculateNumberOfCellsTakenByTrainTracks(
IList<int> rowsOfTrainTracks,
IList<Tuple<int, int>> trainTracks
)
{
var distinctRowsOfTrainTracks = rowsOfTrainTracks.Distinct().ToArray();
Array.Sort(distinctRowsOfTrainTracks);
long sum = 0;
var trainTracksRows = rowsOfTrainTracks.ToArray();
foreach (int row in distinctRowsOfTrainTracks)
{
var numberOfTrainTracks = rowsOfTrainTracks.Count(a => a == row);
int index = 0;
int start = 0;
var trainTracksOnSameRow = new List<Tuple<int, int>>();
while (index < numberOfTrainTracks)
{
int rowIndex = Array.IndexOf(trainTracksRows, row, start);
var trainTrack = trainTracks[rowIndex];
trainTracksOnSameRow.Add(trainTrack);
start = rowIndex + 1;
index++;
}
sum += SumCellsTakenByTrainTracksForSameRow(trainTracksOnSameRow);
}
return sum;
}
/*
* train tracks on same row
* - merge intervals - train track stands for one interval
* - sort train tracks by start column
* - the array is based on start index 1 not 0
* Add all cells taken by train tracks on the same row.
*/
private static long SumCellsTakenByTrainTracksForSameRow(IList<Tuple<int, int>> trainTrackOnSameRow)
{
var trainTracks = trainTrackOnSameRow.ToArray();
IComparer<Tuple<int, int>> myComparer = new MyComparer();
Array.Sort(trainTracks, myComparer);
var previous = trainTracks[0];
long cellsTakensByTrainTracks = 0;
for (int i = 1; i < trainTracks.Length; i++)
{
var current = trainTracks[i];
// no overlap
if (previous.Item2 < current.Item1)
{
cellsTakensByTrainTracks += previous.Item2 - previous.Item1 + 1;
previous = current;
}
// reset the previous
int start = previous.Item1;
int end = Math.Max(previous.Item2, current.Item2);
previous = new Tuple<int, int>(start, end);
}
// edge case: Last one
cellsTakensByTrainTracks += previous.Item2 - previous.Item1 + 1;
return cellsTakensByTrainTracks;
}
}
}