Pretty strange result about skyline problem


  • 0
    H

    I'm trying to solve skyline probem and I submitted a code to OJ. The OJ told me my code failed because of it gave wrong answer in test case :

    input: [[0,2147483647,2147483647]]
    output: [[0,2147483647]]

    And Oj said the expected output should be : [[0,2147483647],[2147483647,0]]

    But I ran my code on my local machine and the output is exactly [[0,2147483647],[2147483647,0]]. I tried both MS VS2010 C++ compiler and GCC compiler and I gt the same result : [[0,2147483647],[2147483647,0]].

    So my question is: why OJ told me the output is [[0,2147483647]] but not [[0,2147483647],[2147483647,0]]. And how can I fix this ?

    Here's my code:

    #include <iostream>
    #include <vector>
    #include <iterator>
    #include <stdlib.h>
    #include <stdio.h>
    
    using namespace std;
    
    
    class Solution {
    public:
        vector<pair<int, int> > getSkyline(vector<vector<int> >& buildings) {
    		vector<pair<int, int> > result;
    		int size = buildings.size();
    		if(size == 0) {
    			//result.push_back(make_pair(0, 0));
    			return result;
    		}
    		int min = (buildings.at(0))[0];
    		int max = (buildings.at(size - 1))[1];
    		int latest = 0;
    		int stencil = 0;
    		for(vector<vector<int> >::iterator outer = buildings.begin(); outer < buildings.end(); outer++)
    		{
    			
    			if((*outer).at(2) == 0) continue;
    			eliminateInner(outer, buildings);
    			for(int i = 0; i < 2; i++) {
    				int x = (*outer).at(i);
    				int highest = innerLoop(x, buildings);
    
    				/*if(highest == 0) {
    					if(result.size() != 0)
    					{
    						result.at(result.size() - 1).second = 0;
    					}
    					latest = 0;
    				} else*/ 
    				if(highest != latest) {
    					result.push_back(make_pair(x, highest));
    					latest = highest;
    				}
    			}
    		}
    
    		return result;
        }
    private:
    	int intersect(const vector<int>& building, int x)
    	{
    		float x_f = x + 0.1;
    		if(x_f>= building[0] && x_f <= building[1]) return building[2];
    		else return 0;
    	}
    	
    	void eliminateInner(vector<vector <int> >::iterator it, vector<vector <int> > & buildings)
    	{
    		for(vector<vector <int> >::iterator inner = it+1; inner < buildings.end(); inner++)
    		{
    			if((*inner).at(2) == 0) continue;
    			if(((*inner).at(2) <= (*it).at(2)) && (*inner).at(0) >= (*it).at(0) && (*inner).at(1) <= (*it).at(1) ) 
    			{ 
    				(*inner).at(2) = 0;
    			}
    		}
    	}
    
    	int innerLoop(int x, vector<vector <int> > & buildings)
    	{
    		int highest = 0;
    		for(vector<vector<int> >::iterator it = buildings.begin(); it < buildings.end(); it++) 
    		{
    			//if(x < (*it).at(0)) break;
    			if((*it).at(2) == 0) continue;
    			//highest = (*outer).at(2);
    							int height = intersect(*it, x);
    			if(height > highest)
    			{
    				highest = height;
    			}
    				
    		}
    		return highest;
    	}
    	
    };
    
    vector<int> make_value(int l, int r, int h) {
    	vector<int> v;
    	v.push_back(l);
    	v.push_back(r);
    	v.push_back(h);
    	return v;
    }
    
    vector<vector<int> > loadData(int data[10000][3] )
    {
    	vector<vector<int> > result;
    	for(int i = 0; i < 10000; i++)
    	{
    		vector<int> v;
    		v.push_back(data[i][0]);
    		v.push_back(data[i][1]);
    		v.push_back(data[i][2]);
    		result.push_back(v);
    	}
    	return result;
    }
    
    int main(void)
    {
    	vector<vector<int> > parameter;
    	vector<int> v = make_value(0, 2147483647,2147483647);
    	parameter.push_back(v);
    	Solution s;
    	vector<pair<int,int> > result = s.getSkyline(parameter);
    	vector<pair<int,int> >::iterator it;
    	for(it = result.begin(); it < result.end(); it++)
    	{
    		cout<<"["<<(*it).first<<","<<(*it).second<<"]"<<" ";
    	}
    	cout<<endl;
    	return 0;
    }

  • 0
    S

    Since our problem is that the last interval [INT_MAX, 0] is not added to result, then either we don't have a line for that, or it is not executed due to some reason. If you can get the expected result on local machine, then the second cause is more likely.

    It is not easy to debug on OJ which does not support printing directly, but you can still do it. For instance, you may return the value of some variables as result, so these numbers will show up in the error message; Another trick is, if the statement responsible for adding the last interval is only executed when a certain condition is met, you need to first make sure if that condition is satisfied or not. You can simply return the 'expected' answer manually when the condition is met. If this modified program passes that particular case due to this addition of manual return, then we know the condition must be met.


  • 0

    "It is not easy to debug on OJ which does not support printing directly"

    When was the last time you tried? I've been printing for debugging here for a while.


  • 0

    Printing to stdout should be working for over a month now, I should update the FAQ... This is the first step to make online debugging easier, please stay tuned for more debugging features soon.


  • 0
    S

    It is good to know we already have this feature online! Now you see how fast LCOJ evolves. One month away from it and I already can't keep up...


  • 0

    Welcome back @stellari! We have more exciting features coming up!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.