Time limit exceeded even though all test cases passed


  • 0
    T

    Perfect Rectangle

    All 46 / 46 test cases are reported to pass. But it still gives a time limit exceeded.

    I have similar issues with another problem too.

    Looks like leetcode doesn't care about C#.


  • 0

    @tachyon77 Could you please post your C# code here so I can fix it? Also, I have moved your topic to the correct category, the "Interview Questions" category is for posting interview questions only.


  • 0
    T

    public class Rectangle
    {
    public int X1, X2, Y1, Y2;

        public bool OverlapsWith ( Rectangle other )
        {
            if ( Y1 < other.Y1)
                return (X2 > other.X1) && (Y2 > other.Y1);
            return (X2 > other.X1) && (other.Y2 > Y1);
        }       
        public int Area
        {
            get
            {
                return (X2 - X1) * (Y2 - Y1);
            }
        }
    }
    
    public class Solution
    {
        
        public bool IsRectangleCover(int[,] rectangles)
        {
            var allRectangles = new List<Rectangle>();
    
            var firstRectangle = new Rectangle()
            {
                X1 = rectangles[0, 0], Y1 = rectangles[0, 1],
                X2 = rectangles[0, 2], Y2 = rectangles[0, 3]
            };
    
            allRectangles.Add(firstRectangle);
            var coveringRectangle = new Rectangle()
            {
                X1 = rectangles[0, 0],
                Y1 = rectangles[0, 1],
                X2 = rectangles[0, 2],
                Y2 = rectangles[0, 3]
            };
    
            var totalArea = firstRectangle.Area;
    
            var N = rectangles.GetLength(0);
            for (int i = 1; i < N; ++i)
            {
                var rectangle = new Rectangle()
                {
                    X1 = rectangles[i, 0],
                    Y1 = rectangles[i, 1],
                    X2 = rectangles[i, 2],
                    Y2 = rectangles[i, 3]
                };
    
                allRectangles.Add(rectangle);
                totalArea += rectangle.Area;
    
                if ((rectangle.X1 <= coveringRectangle.X1) && (rectangle.Y1 <= coveringRectangle.Y1))
                {
                    coveringRectangle.X1 = rectangle.X1;
                    coveringRectangle.Y1 = rectangle.Y1;
                }
    
                if ((rectangle.X2 >= coveringRectangle.X2) && (rectangle.Y2 >= coveringRectangle.Y2))
                {
                    coveringRectangle.X2 = rectangle.X2;
                    coveringRectangle.Y2 = rectangle.Y2;
                }
            }
    
            if (totalArea != coveringRectangle.Area)
                return false;
    
    
            // Sort by BottomLeft.X
    
            var rectanglesSortedByLeftEdge = allRectangles.OrderBy(x => x.X1).ToArray();
    
            for (int i =0; i<N; ++i)
            {
                var rectangle = rectanglesSortedByLeftEdge[i];
    
                for (int j=i+1; j<N; ++j)
                {
                    var adjacentRectangle = rectanglesSortedByLeftEdge[j];
    
                    if (adjacentRectangle.X1 >= rectangle.X2)
                        break;
    
                    if (rectangle.OverlapsWith(adjacentRectangle))
                        return false;
                }
            }
    
    
            return true;
    
        }
    }

  • 0

    @tachyon77 Done. Your code should get AC now.


Log in to reply
 

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