We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Gridland Metro
  5. Discussions

Gridland Metro

Sort by

recency

|

412 Discussions

|

  • paramjeetsharan1
     + 0 comments

    // where i am doing wrong

    public static long gridlandMetro(int n, int m, int k, List<List<Integer>> track) {
    Map<Integer,int[]> realPath = new HashMap<>();
    long result = 0;
    for(int i =0;i<k;i++){
        List<Integer> l1 = track.get(i);
        int row = l1.get(0);
        int c1 = l1.get(1);
        int c2 = l1.get(2);
        if(realPath.containsKey(row)){
             int[] coloums = realPath.get(row);
            int c21 = coloums[0];
            int c22 = coloums[1];
            if(c21>c1){
               coloums[0] = c1;
            }
            if(c22<c2){
                coloums[1] = c2;
            }
            realPath.put(row, coloums);
        }else{
            int[] coloums = new int[2];
            coloums[0] = c1;
            coloums[1] = c2;
            realPath.put(row, coloums);
        }
    }
    for(int i =1;i<=n;i++){
        if(realPath.containsKey(i)){
            int[] coloums = realPath.get(i);
            int c21 = coloums[0];
            int c22 = coloums[1];
            int incr = (m+c21)-(c22+1);
            result+=incr;
        }else{
            result+=m;
        }
    }
    return result;
}

  • dehaka
     + 1 comment
    long gridlandMetro(long n, long m, int k, vector<vector<int>> track) {
    if (track.empty()) return n * m;
    long lamppost = 0;
    sort(track.begin(), track.end());
    int currentRow = track[0][0], trackCell = 0, lastEnd = 0, rowCounter = 1;
    for (int i=0; i < track.size(); i++) {
        if (track[i][0] != currentRow) {
            lamppost = lamppost + m - trackCell;
            currentRow = track[i][0];
            trackCell = 0;
            lastEnd = 0;
            rowCounter++;
        }
        if (i < track.size()-1 and track[i+1][0] == currentRow and track[i][1] == track[i+1][1]) continue;
        trackCell = trackCell + track[i][2] - track[i][1] + 1;
        trackCell = (track[i][1] <= lastEnd) ? (trackCell - min(lastEnd-track[i][1]+1, track[i][2]-track[i][1]+1)) : trackCell;
        lastEnd = max(lastEnd, track[i][2]);
    }
    lamppost = lamppost + m - trackCell + m * (n - rowCounter);
    return lamppost;
}

    O(n) except for the sort line

  • gtai_quant
     + 1 comment
    from collections import defaultdict

def gridlandMetro(n, m, k, track):
    
    row_record = defaultdict(list)
    for r, c1, c2 in track:
        if r not in row_record:
            row_record[r] = [c1, c2]
        else:
            st, ed = row_record[r][0], row_record[r][1]
            if c1 > ed:
                row_record[r][1] += c2 - c1 + 1
            else:
                row_record[r][1] = max(ed, c2)
            if c2 < st:
                row_record[r][0] -= c2 - c1 + 1
            else:
                row_record[r][0] = min(st, c1)
            
    total_num = n * m
    for st, ed in row_record.values():
        total_num -= ed - st + 1
        
    return total_num

  • cb_kalz
     + 0 comments
    def gridlandMetro(n: Int, m: Int, k: Int, track: Array[Array[Int]]): Long = {
    var ans = 1L * n*m
    track.groupBy(_(0)).values.foreach{ x =>
        x.sortInPlaceBy{_(1)}
        var (l,r) = (x.head(1), x.head(2)) 
        x.tail.foreach { t => (t(1),t(2)) match {
              case (a,b) if a > r =>
                ans -= (r - l + 1)
                l = a
                r = b
              case (_,b) => r = r.max(b)
            }
        }
        ans -= (r - l + 1)
    }
  ans
}

  • aldufc
     + 0 comments

    Ruby

    def gridlandMetro(n, m, k, track)
    minMax = Hash.new(-1)
    track.each do |line|
        minMax[line[0]] = [] if minMax[line[0]] == -1            
        minMax[line[0]] << [line[1], line[2]] 
    end
    counter = 0
    minMax.values.each do |line|
        line.sort!        
        while not line.empty?
            start_point, end_point = line.shift        
            end_point = [line.shift[1], end_point].max while not line.empty? and line[0][0] <= end_point
            counter += end_point - start_point + 1
        end        
    end
    m*n - counter
end