D
DevExCode

LeetCode 1847: Closest Room Solution

Master LeetCode problem 1847 (Closest Room), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can sort the rooms by size in descending order. Then, for each query, we iterate through the sorted rooms and find the closest room that meets the size requirement. We can use a TreeSet in Java or a set in C++ and Python to efficiently find the closest room based on the preferred room number.

  1. Sort the rooms by size in descending order.
  2. For each query:
    • Iterate through the sorted rooms.
    • Use a TreeSet (Java) or a set (C++/Python) to efficiently find the closest room based on the preferred room number.
    • Check if the room meets the size requirement.
    • Update the answer accordingly.

Time Complexity: O((n + k) * log n) where n is the number of rooms and k is the number of queries. Sorting the rooms takes O(n * log n) time, and processing each query takes O(log n) time for finding the closest room.

Space Complexity: O(n) for storing the sorted rooms.

Solution Code

import java.util.*;

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        Arrays.sort(rooms, (a, b) -> Integer.compare(b[1], a[1]));
        TreeSet<Integer> roomIds = new TreeSet<>();
        int[] result = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int preferred = queries[i][0];
            int minSize = queries[i][1];
            int closestRoomId = -1;
            int minDiff = Integer.MAX_VALUE;

            for (int[] room : rooms) {
                if (room[1] < minSize) {
                    break;
                }
                if (roomIds.contains(room[0])) {
                    continue;
                }

                int diff = Math.abs(room[0] - preferred);
                if (diff < minDiff || (diff == minDiff && room[0] < closestRoomId)) {
                    closestRoomId = room[0];
                    minDiff = diff;
                }
            }

            result[i] = closestRoomId;
            if (closestRoomId != -1) {
                roomIds.add(closestRoomId);
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1847 (Closest Room)?

This page provides optimized solutions for LeetCode problem 1847 (Closest Room) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1847 (Closest Room)?

The time complexity for LeetCode 1847 (Closest Room) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1847 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1847 in Java, C++, or Python.

Back to LeetCode Solutions