# Gridland Metro challenge

### Problem statement

The city of Gridland is represented as an matrix where the rows are numbered from to and the columns are numbered from to .

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 and , where represents the row number, represents the starting column, and 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 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 (the number of rows), (the number of columns), and (the number of train tracks).

Each line of the subsequent lines contains three space-separated integers describing the respective values of , , and that define a train track.

**Constraints**

–

–

–

–

**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 as our answer.

### Solution Concept

The maximum number of cells where the mayor can place lampposts is . Next we group each input by . For that we use a dictionary `map`

with `map[row]`

holding a list of intervals for . For instance, if our input looks as follows:

4 4 4 2 2 3 3 1 4 4 4 4 3 2 3

our `map`

will look as follows:

map[1] -> [] map[2] -> [[2,3]] map[3] -> [[1,4],[2,3]] map[4] -> [[4,4]]

Note that the first row is our problem configuration ( and ).

This map can be constructed in time.

Next, we iterate over our `map`

and *merge* the interval list in case of any overlapping intervals. For instance, if we have the folloing interval list:

[1,3],[2,6],[8,10],[15,18]

the merged list will looks as follows:

[1,6],[8,10],[15,18]

Next, once we have a *merged* the interval list for each in `map`

, all that is left to do ist sum the number of columns each interval list occupies for each in `map`

and subtract it from . For example, the following interval list:

[1,6],[8,10],[15,18]

occupies columns.

Finaly, return .

import sys from collections import defaultdict """ Class representing an interval with start and end position. """ class Interval: def __init__(self, start, end): self.start = start self.end = end def __eq__(self, other): return self.start == other.start def __lt__(self, other): return self.start < other.start def __repr__(self): return "[%s, %s]" % (self.start, self.end) """ Given a collection of intervals, merges all overlapping intervals. Sample Input: [1,3],[2,6],[8,10],[15,18] Output: [1,6],[8,10],[15,18] """ def merge(intervals): # Sort all intervals in decreasing order of start time. intervals.sort(reverse=True) n = len(intervals) cursor = 0 for i in range(0, n): if (cursor != 0 and intervals[i].end >= intervals[cursor-1].start): while (cursor != 0 and intervals[i].end >= intervals[cursor-1].start): # While current interval overlaps with previous interval --> Merge intervals[cursor-1].start = min(intervals[cursor-1].start, intervals[i].start) intervals[cursor-1].end = max(intervals[cursor-1].end, intervals[i].end) cursor -= 1 else: intervals[cursor] = intervals[i] cursor += 1 return intervals[:cursor] """ Given a collection of disjunct intervals it returns the total space occupied by those intervals. Sample Input: [1,6],[8,10],[15,18] Output: 13 """ def countOccupied(intervals): ans = 0 for interval in intervals: ans += (interval.end - interval.start + 1) return ans def main(): f = open("in.txt") n, m, k = (int(i) for i in f.readline().split()) map = defaultdict(list) for i in range(0, k): row, c1, c2 = (int(i) for i in f.readline().split()) map[row].append(Interval(c1,c2)) total = n*m for row in map: map[row] = merge(map[row]) total -= countOccupied(map[row]) print(total) main()

**Notebook file**

https://github.com/lucaslouca/coding-problems/tree/master/python/GridlandMetro