ग्रिडलैंड मेट्रो हैकररैंक जावा

प्रश्न में बाधा 1<=n,m<=10^9 हैं।

आप इतने आकार के द्वि-आयामी सरणी की घोषणा नहीं कर सकते क्योंकि इसके लिए बड़ी मात्रा में ढेर स्थान की आवश्यकता होगी, उदाहरण के लिए यदि n,m दोनों 10^9 हैं, तो गिरफ्तारी का आकार 10^18 * 4 /( 1024 * 1024 * 1024) Gb होगा।

इस बड़े सरणी का उपयोग किए बिना इस प्रश्न को हल किया जा सकता है। अगर आपको सही दृष्टिकोण के साथ किसी मदद की ज़रूरत है तो मैं मदद कर सकता हूं, लेकिन पहले स्वयं प्रयास करें।

मैंने हैश मैप का उपयोग करके यह समाधान लिखा है, मैं एक नक्शा बनाए रख रहा हूं इंटीजर पंक्ति संख्या है और हैशसेट विशेष पंक्ति के लिए देखे गए कॉलम का सेट है। यह नक्शा यह जांचने के लिए रखा जाता है कि कहीं कोई ओवरलैपिंग ट्रैक तो नहीं है। कोड छोटे परीक्षण मामलों पर सही उत्तर देता है। लेकिन, अधिकांश परीक्षण मामलों में, यह समय समाप्त होने के कारण विफल हो जाता है। इस कोड को अनुकूलित करने में किसी भी मदद की अत्यधिक सराहना की जाती है।

    import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long m = sc.nextInt();
        int k = sc.nextInt();        
        HashMap<Integer,HashSet> map = new HashMap<Integer,HashSet>(); 
        long count = n*m;
        for (int i =0;i<k;i++)
            {
            HashSet<Integer> set = new HashSet<Integer>();    
            int row = sc.nextInt();
            int c1 = sc.nextInt();
            int c2 = sc.nextInt();
            //System.out.println(row+" "+ c1+" "+c2);
            if (map.containsKey(row))
                {
                set = map.get(row);
                for (int j = c1;j<=c2;j++)
                {
                    if(set.add(j)) count--;
                }
                //if (set.add(c2)) count--;
                map.put(row,set);
            }
                else
                {
                    for (int p = c1;p<=c2;p++)
                    {
                        if (set.add(p)) count --;
                    }
                    //if (set.add(c2)) count--;

                    map.put(row,set);
                }
        }
        System.out.println(count);

    }
    }

मैं यहाँ समाधान प्रदान नहीं करने जा रहा हूँ क्योंकि मुझे नहीं लगता कि यह HackerRank की भावना में है। हालाँकि, मैंने कुछ संकेत दिए हैं और आपके कोड की समस्याओं की पहचान की है।

Scanner input = new Scanner(System.in);
int n = input.nextInt();//ERROR: n ranges from 1 to 10E9, read in as a String
int m = input.nextInt();//ERROR: m ranges from 1 to 10E9, read in as String
int k = input.nextInt();
int[][] arr = new int[n][m];/*ERROR: The range of an int is 2E31-1 and large 
                                    integers will cause stack overflow anyway. 
                                    You'll need to consider a data structure 
                                    that's compatible w/ strings. Hint, consider 
                                    a hash table. */
int occupied = 0;
for (int i = 0; i < n; i++) {
    Arrays.fill(arr[i], 0);
}
for (int i = 0; i < k; i++) {
    int r = input.nextInt() - 1;//ERROR: r ranges from 1 to 10E9, read in as a String
    int c1 = input.nextInt() - 1;//ERROR: c1 ranges from 1 to 10E9, read in as a String
    int c2 = input.nextInt() - 1;//ERROR: c2 ranges from 1 to 10E9, read in as a String
    for (int j = c1; j <= c2; j++) {
        arr[r][j] = -1;
    }
}
/* NOTE: A train track may (or may not) overlap other train tracks within the 
     same row. Hence, your algorithm will need to account for track overlaps 
     and tracks that are in between of each other. For example, if a track 
     overlaps with another track in the same the row, the tracks should be 
     merged into a single track. If a smaller track is contained in a bigger 
     track, the smaller track should be ignored.*/
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (arr[i][j] != -1) {
            count++;
        }
    }
}

System.out.println(count);