Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Gridland Metro challenge

Sharing is caring!

Problem statement

The city of Gridland is represented as an n \times m matrix where the rows are numbered from 1 to n and the columns are numbered from 1 to m.

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

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

Constraints
1 \le n,m \le 10^9
0 \le k \le 1000
1 \le r \le n
1 \le c_1 \le c_2 \le 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

gridland-metro

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.

Solution Concept

The maximum number of cells where the mayor can place lampposts is total = nm. Next we group each input (row, c_1, c_2) by row. For that we use a dictionary map with map[row] holding a list of intervals (c_1, c_2) for row. 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 (n,m and k).
This map can be constructed in \mathcal{O}(k) 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 row in map, all that is left to do ist sum the number of columns each interval list occupies for each row in map and subtract it from total. For example, the following interval list:

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

occupies 13 columns.

Finaly, return total.

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